背景

有人写了一个RSA加密给我玩。

描述

我赌5毛前面两题的内容也就开头几句话平时会用到。

还是做点具体的东西吧。

求c^d Mod N

输入格式

三个用空格隔开的整数c,d,N

输出格式

一个整数表示答案

样例输入

1 2 6

样例输出

1

数据范围与约定

  • 对于前30%的数据:1\leq c,d< N,N=13*17
  • 对于后70%的数据:1\leq c< N, 1\leq d\leq 10^{1000000}, N=10^9+7