template<class T1, class T2>static mint Pow(T1 x, T2 n)
繰り返し二乗法で を計算する 計算量
namespace LIB { template<long long mod>class ModINT { using mint=ModINT; using ll=long long; ll inv(ll a, ll m) { ll b=m,u=1,v=0; while(b) { ll t=a/b; a-=t*b,swap(a,b); u-=t*v,swap(u,v); } u%=m; return (u<0)?u+m:u; } public: ll x; NT_ModINT() : x(0) {} NT_ModINT(ll init) : x(init% mod + mod) { if (x >= mod) x -= mod; } mint operator + () const { return x; } mint operator - () const { return (-x < 0) ? mod - x : -x; } mint& operator += (mint r) { if ((x += r.x) >= mod) x -= mod; return *this; } mint& operator -= (mint r) { if ((x -= r.x) < 0) x += mod; return *this; } mint& operator *= (mint r) { x = (unsigned long long) x * r.x % mod; return *this; } mint& operator /= (mint r) { x = x * Inv(r.x, mod) % mod; return *this; } mint& operator += (ll r) { return *this += mint(r); } mint& operator -= (ll r) { return *this -= mint(r); } mint& operator *= (ll r) { return *this *= mint(r); } mint& operator /= (ll r) { return *this /= mint(r); } template <class T> mint operator + (T r) const { return mint(*this) += r; } template <class T> mint operator - (T r) const { return mint(*this) -= r; } template <class T> mint operator * (T r) const { return mint(*this) *= r; } template <class T> mint operator / (T r) const { return mint(*this) /= r; } friend ostream& operator << (ostream& s, mint a) { s << a.x, a.x %= mod; return s; } friend istream& operator >> (istream& s, mint& a) { s >> a.x, a.x %= mod; return s; } bool operator == (mint& r) const { return x == r.x; } bool operator != (mint& r) const { return x != r.x; } bool operator < (mint& r) const { return x < r.x; } bool operator <= (mint& r) const { return x <= r.x; } bool operator > (mint& r) const { return x > r.x; } bool operator >= (mint& r) const { return x >= r.x; } template <class T1, class T2> static mint Add(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) + mint(r); } template <class T1, class T2> static mint Sub(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) - mint(r); } template <class T1, class T2> static mint Mul(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) * mint(r); } template <class T1, class T2> static mint Div(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) / mint(r); } template<class T1, class T2>static mint Pow(T1 x, T2 n) { mint res=1; if(0<n) { res=Pow(x,n/2); res=res*res; if(n%2!=0) res*=x; } return res; } }; }
