Original Description

給三個正整數 $a,b,c$ ，求 $a^ {b^ c} \bmod 880301$ 。 （880301是一個質數）

Original Input Format

輸入的第一行包含三個用空白分隔的正整數 $a,b,c$ 。

• $1 \le a,b,c \le 1000000000$

Original Output Format

請輸出一個數字，代表 $a^ {b^ c} \bmod 880301$ 的值。

Original Sample Input

2 2 2

Original Sample Output

16

Original Limits

• Time Limit: 1 second
• Memory Limit: 256 MB

Program To Be Hacked

#include<iostream>
using namespace std;
long long mypow(long long A,long long B,long long M){ //calculate A^B % M
    A%=M;
    if(M==1) return 0;
    if(B==0) return 1;
    if(A==0) return 0;
    long long mid=mypow(A,B/2,M);
    if(B%2) return mid*mid%M*A%M;
    else return mid*mid%M;
}
int main(){
    long long a,b,c,p=880301;
    cin>>a>>b>>c;
    cout<<mypow(a,mypow(b,c,p-1),p)<<'\n';
}

Judge Method

學過快速冪的學姐一看就知道這題只要做兩次快速冪就好了，於是她寫出了一個快速冪函數

long long mypow(long long A,long long B,long long M){ //calculate A^B % M
    A%=M;
    if(M==1) return 0;
    if(B==0) return 1;
    if(A==0) return 0;
    long long mid=mypow(A,B/2,M);
    if(B%2) return mid*mid%M*A%M;
    else return mid*mid%M;
}

另外由費馬小定理，我們知道

$a^ {b^ c} \equiv a^ {b^ c \bmod (p-1)} \pmod p$

所以我們只需計算 $\text{mypow} (a, \text{mypow} (b,c,p-1),p)$ 就好了。

但這份程式碼卻是有問題的，請找出一個讓這份程式碼得出錯誤答案的測試資料!

Sample Code

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。

#include <cstdio>
int main() {
    printf("1 1 1\n");
}