#include using namespace std; #define ll long long #define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++) #define rrep(i, n, a) for (int i = (int)(n); i >= (int)(a); i--) const int P = 998244353; void solve(){ ll n,p; cin >> n >> p; int e = 0; while(n > 0){ e += n/p; n /= p; } string s = ""; while(e > 0){ if(e % 2 == 0){ s+='0'; } else{ s+='1'; } e /= 2; } ll ans = 1; for(int i = s.size()-1;i >= 0;i--){ ans = (ans*ans)%P; if(s[i] == '1'){ ans = (ans*p)%P; } } cout << ans; } int main(){ solve(); return 0; }