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