輸入正整數 $x$, $y$ 與 $p$，計算 $x^{y}modp$ $y$, $p$ 皆不超過 ${10}^9+9$，但 $x$ 的範圍是不超過 200 位的正整數

輸入格式

輸出格式

範例輸入

123456789012345678901234567890 5 11

範例輸出

10