#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define MOD2 998244353
#define INF 1000000007
#define LINF 1000000000000000007LL
#define PI 3.14159265359
#define P pair<ll,ll>
template <typename T>
inline bool chmax(T &a, const T &b){
    if(a<b) {a=b; return true;}
    else return false;
}
template <typename T>
inline bool chmin(T &a, const T &b){
    if(a>b) {a=b; return true;}
    else return false;
}
struct Edge{
    int to; ll cost;
    Edge(int to, ll cost) : to(to), cost(cost) {}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph &g,int from,int to,ll cost,bool rev,ll rev_cost){
    g[from].push_back(Edge(to,cost));
    if(rev) g[to].push_back(Edge(from,rev_cost));
}
 
//xのn乗
ll mod_pow(ll x, ll n, ll mod) {// O(log(n))
    ll res = 1;
    while (n > 0) {//繰り返し二乗法
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
//xの逆元を計算する
ll mod_inv(ll x, ll mod) {//O(log(mod))
    return mod_pow(x, mod - 2, mod);
}

 
void solve(){
    ll a,n;
    cin>>a>>n;
    cout<<10000000<<endl;
    cout<<mod_pow(a,n,10000000)<<endl;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<setprecision(10)<<fixed;
    solve();
    return 0;
}