题意不再赘述
具体运用见初等数论
/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1111111111
#define MAXN 111111
#define MAXM 444444
#define PI acos(-1.0)
#define L(X) X<<1
#define R(X) X<<1|1
using namespace std;
long long mod = 100000000LL;
long long euler(long long n)
{long long x = n;long long phi = n;for (long long i = 2; i * i <= x; i++){if (x % i == 0){phi = phi / i * (i - 1) ;while (x % i == 0) x /= i;}}if (x != 1) phi = phi / x * (x - 1);return phi;
}long long fastmod(long long a, long long b, long long c)//a^b mod c
{long long ret = 1;a %= c;for (; b; b >>= 1, a = (a * a) % c)if (b & 1)ret = (ret * a) % c;return ret;
}
long long solve(long long a, long long b, long long c)
{long long t = euler(c);if(b == 1) return a % c;else return fastmod(a, solve(a, b - 1, t) + t, c);
}
int main()
{long long a, k;while(scanf("%I64d%I64d", &a, &k) != EOF){if(a == 0 && k % 2 == 0) {puts("1"); continue;}printf("%I64d\n", solve(a, k, mod));}return 0;
}