輸入正整數 \(x\), \(y\) 與 \(p\)，計算 \(x^y \bmod p\) \(y\), \(p\) 皆不超過 \(10^9 + 9\)，但 \(x\) 的範圍是不超過 200 位的正整數

輸入格式

輸出格式

範例輸入

123456789012345678901234567890 5 11

範例輸出

10