#include <bits/stdc++.h> #define ll long long using namespace std; #define all(v) v.begin(), v.end() int main() { ll a,n; cin >> a >> n; ll ans = 1;//n=10000018なら1 n++; n %= 10000018; for(ll i=1;i<n;i++){ ans %= 10000019; ans *= a; ans %= 10000019; } cout << 10000019 << endl << ans << endl; }