#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 %= 10000019;
    for(ll i=1;i<n;i++){
        ans %= 10000019;
        ans *= a;
        ans %= 10000019;
    }
    cout << 10000019 << endl << ans << endl;
}