e040. Q-2-13. 無理數的快速冪 (108 高中全國賽, simplifed)

Content

若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 秒

Input

一行含三個正整數，依序為 x, y 與 n，以空格隔開。

Output

s 與 t，中間空一格。

Sample Input

2 3 2

Sample Output

22 12

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

Hint ：

Tags:

出處:

[管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」