### 问题描述 小明最近被数学折磨到头秃，老师看到小明的痛苦决定出一道数学题安慰小明。这题说的是有关系式 ${a}^{bc}$ 与 $x$ 模 $9999991$ 同余（同余是指两个数在除以一个正整数时余数相等），求小于 $9999991$ 最小正整数 $x$，小明当场崩溃，聪明的你能帮助小明逃离苦海嘛？ ### 输入格式 第一行输入 $3$ 个整数，分别表示 $a,b,c$。 ### 输出格式 输出仅一行，包含一个整数，表示答案 $x$。 ### 样例输入 ```text 90 2 2 ``` ### 样例输出 ```text 5610054 ``` ### 评测数据规模与样例说明 样例说明：代入样例数值得 ${a}^{bc} = 65610000$，$65610000 \% 9999991 = 5610054$，显然答案 $x$ 为 $5610054$。 对于所有评测数据，$1 \leq a,b,c \leq {10}^{8}$。