#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=998244353;
struct node {...node operator*(const node &o) const {...}
};
node qpow(node a,int b) {node ans=...;while(b) {if(b&1) ans=ans*a;a=a*a;b>>=1;}return ans;
}
node euclid(int a,int b,int c,int n,node U,node R) {if(b>=c) return qpow(U,b/c)*euclid(a,b%c,c,n,U,R);if(a>=c) return euclid(a%c,b,c,n,U,qpow(U,a/c)*R);int m=(a*n+b)/c;if(!m) return qpow(R,n);return qpow(R,(c-b-1)/a)*U*euclid(c,(c-b-1)%a,a,m-1,R,U)*qpow(R,n-(c*m-b-1)/a);
}
