题目描述

费马小定理：假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。 所以根据上述定理我们可以对于求解y^n%p类问题，我们可以对n进行降幂求解。 下面我们在综合实践一下，求解3^(a^a)%101。

输入格式

测试数据包含多组输入 每组输入共一行，包含一个整数a (1<a<1e9)

输出格式

对于每组输入输出一行答案表示3^(a^a)%101的值

1
2

3
81