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