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