若 \(s + t\sqrt{2} = (x + y\sqrt{2})^n\)，其中 \(x, y, s, t\) 均為正整數 輸入 \(x\), \(y\) 與 \(n\) 請計算並輸出 \(s\) 與 \(t\) 除以 \(p\) 的餘數 \(p=10^9+9\) 且 \(x,y,n < p\)

輸入格式

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

輸出格式

\(s\) 與 \(t\)，中間空一格。

範例輸入

2 3 2

範例輸出

22 12