对于给定的整数 和高精度整数 ，计算 的值。由于答案可能很大，请将答案对整数 取模后输出。

输入描述:

第一行输入一个整数 ，表示底数。第二行输入一个高精度整数 ，表示指数。第三行输入一个整数 ，表示模数。

输出描述:

输出一个整数，表示 的值对 取模后的结果。

备注:

本题数据量较大，我们建议您选取较快的读入方式。