若s + t√2 = (x + y√2)^n ，其中 x, y, s, t 均為正整數，輸入 x,y 與 n，請計算並輸出 s 與 t 除以 p 的餘數。p=10e9+9 且 x,y,n < p。
Time limit: 1 秒
一行含三個正整數，依序為 x, y 與 n，以空格隔開。
s 與 t，中間空一格。
2 3 2
22 12