輸入正整數 \(x\), \(y\) 與 \(p\)，計算 \(x^y \bmod p\)。\(x\), \(y\), \(p\) 皆不超過 \(10^9 + 9\)。例如 \(x=2,y=5, p=11\)，則答案是\(10\)。

輸入格式

輸入 \(x\), \(y\) 與 \(p\) 在同一行，以空白間隔，行尾可能有空格。

輸出格式

輸出計算結果。

範例輸入

2 5 11

範例輸出

10