/* -*- coding: utf-8 -*- * * 747.cc: No.747 循環小数N桁目 Hard - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int M = 6; const char ds[] = "285714"; const int MAX_N = 100000; /* typedef */ /* global variables */ char sn[MAX_N + 1], sk[MAX_N + 1]; int v0[MAX_N], v1[MAX_N]; /* subroutines */ int s2v(char s[], int v[]) { int n = strlen(s); for (int i = 0; i < n; i++) v[i] = s[n - 1 - i] - '0'; return n; } int remv(int n, int v[]) { int rem = 0; for (int i = n - 1; i >= 0; i--) rem = (rem * 10 + v[i]) % M; return rem; } void shiftv(int &n, int v[]) { int co = 0; for (int i = n - 1; i >= 0; i--) { int d = co * 10 + v[i]; v[i] = (d >> 1); co = (d & 1); } while (n > 0 && v[n - 1] == 0) n--; } int pown(int a, int b) { int p = 1; while (b) { if (b & 1) p = p * a % M; a = a * a % M; b >>= 1; } return p; } int powv(int a, int n, int v[]) { // a^v int p = 1; for (int i = 0; i < n; i++) { p = p * pown(a, v[i]) % M; a = pown(a, 10); } return p; } /* main */ int main() { scanf("%s%s", sn, sk); int n0 = s2v(sn, v0); int n1 = s2v(sk, v1); int a = remv(n0, v0); int b = powv(a, n1, v1); //printf("a=%d, b=%d\n", a, b); printf("%c\n", ds[(b + M - 1) % M]); return 0; }