#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
#define QUICKINV
template < class S, int ID > class DymanicModInt
{
	static_assert(is_same < S, int > :: value || is_same < S, long long > :: value);
public:
	using U = conditional_t < is_same < S, int > :: value, unsigned, unsigned long long >; static U P;
private:
	using D = conditional_t < is_same < S, int > :: value , unsigned long long, __uint128_t >;
	inline static U uinv(U x) { U y = x; for ( int i = is_same < S, int > :: value ? 4 : 5 ; i-- ; ) y *= 2 - x * y; return y; }
	static U P2, R, R2;
	inline constexpr static U reduce(D x) { return ( x + (U)x * R * (D)P ) >> ( sizeof(U) * 8 ); }
	inline DymanicModInt(U x, int) : v(x) {} U v;
#ifdef QUICKINV
	struct inv_helper_T{
		inline static constexpr int K = sizeof(S) * 8 / 3;
		inline static constexpr S B = ((S)1) << K, T = B << K;
		S f[T + 1], g[T + 1]; U buf[T * 3 + 1], *I = buf + T, h[T + 1];
		inline constexpr void init(){
			fill_n(f + 1, T, 0);
			for (S i = 1; i <= B ; i++ ){
				S s = 0, d = (i << K);
				for(U j = 1; j <= T ; j++ ){
					if ((s += d) >= mod()) s -= mod();
					if (s <= T) {
						if (!f[j]) f[j] = i, g[j] = s;
					}
					else if (s >= mod() - T) {
						if (!f[j]) f[j] = i, g[j] = s - mod();
					}
					else{
						const U t = (mod() - T - s - 1) / d;
						s += t * d, j += t;
					}
				}
			}
			f[0] = 1, I[0] = 0, I[1] = reduce(R2);
			for (S i = 2; i <= T + T; i++ ) I[i] = reduce((D)reduce((D)R2 * (mod() / i)) * ( P2 - I[mod() % i] ));
			for (S i = 1; i <= T; i++ ) buf[T - i] = P2 - I[i];
			for (S i = 0; i <= T; i++ ) h[i] = reduce((D)R2 * f[i]);
		}
		inline DymanicModInt inv(const S&x) const{
			return DymanicModInt(reduce((D)I[g[x >> K] + x % B * f[x >> K]] * h[x >> K]), 0);
		}
	};
	inline static inv_helper_T inv_helper;
#endif
public:
	inline static void set_mod(S p) { 
		assert(p & 1 && 0 < p && p < ( (S)1 << ( sizeof(S) * 8 - 2 ) )), P = p, P2 = P << 1, R = -uinv(P), R2 = -(D)P % P, assert(P * R == -1); 
#ifdef QUICKINV
		inv_helper.init();
#endif
	}
	inline static S mod() { return P; }
	inline DymanicModInt() : v(0) {}
	inline DymanicModInt(const DymanicModInt &x) : v(x.v) {}
	template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 > inline constexpr DymanicModInt(T x) { if constexpr ( numeric_limits < T >::is_signed ) if ( __builtin_expect(x < 0, false) ) { __builtin_expect(x + P < 0, false) && ( x %= P ), v = reduce((D)R2 * (U)( x + P )); return; } if constexpr ( sizeof(T) > sizeof(U) ) __builtin_expect(x >= (T)1 << sizeof(U), false) && ( x %= P ); v = reduce((D)R2 * (U)x); }
	inline S val()const { U x = reduce(v); return ( x - P ) >> ( sizeof(U) * 8 - 1 ) ? x : x - P; }
	template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 > explicit inline operator T()const { return val(); }
	inline friend bool operator==(const DymanicModInt &x, const DymanicModInt &y) { return x.val() == y.val(); }
	inline friend bool operator!=(const DymanicModInt &x, const DymanicModInt &y) { return x.val() != y.val(); }
	inline DymanicModInt &operator=(const DymanicModInt &x) & { v = x.v; return *this; }
	inline DymanicModInt &operator++() & { v == P2 - 1 ? v = 0 : v++; return *this; }
	inline DymanicModInt operator++(int) & { DymanicModInt x = *this; v == P2 - 1 ? v = 0 : v++; return x; }
	inline DymanicModInt &operator--() & { v ? v-- : v = P2 - 1; return *this; }
	inline DymanicModInt operator--(int) & { DymanicModInt x = *this; v ? v-- : v = P2 - 1; return x; }
	inline DymanicModInt operator-()const { return DymanicModInt(v ? P2 - v : 0, 0); }
	inline DymanicModInt &operator+=(const DymanicModInt &x) & { v += x.v, ( v - P2 ) >> ( sizeof(U) * 8 - 1 ) || ( v -= P2 ); return *this; }
	inline DymanicModInt &operator-=(const DymanicModInt &x) & { v -= x.v, v >> ( sizeof(U) * 8 - 1 ) && ( v += P2 ); return *this; }
	inline DymanicModInt &operator*=(const DymanicModInt &x) & { v = reduce((D)v * x.v); return *this; }
	inline DymanicModInt &operator/=(const DymanicModInt &x) & { return *this *= x.inv(); }
	inline friend DymanicModInt operator+(DymanicModInt x, const DymanicModInt &y) { return x += y; }
	inline friend DymanicModInt operator-(DymanicModInt x, const DymanicModInt &y) { return x -= y; }
	inline friend DymanicModInt operator*(DymanicModInt x, const DymanicModInt &y) { return x *= y; }
	inline friend DymanicModInt operator/(DymanicModInt x, const DymanicModInt &y) { return x /= y; }
	template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 > inline DymanicModInt qpow(T y)const { DymanicModInt x = *this, z = 1; while ( y ) { if ( y & 1 ) z *= x; if ( y >>= 1 ) x *= x; } return z; }
	template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 > inline friend DymanicModInt qpow(const DymanicModInt &x, T y) { return x.qpow(y); }
#ifdef QUICKINV
	inline constexpr DymanicModInt inv() { return inv_helper.inv(val()); }
	inline constexpr friend DymanicModInt inv(DymanicModInt x) { return x.inv(); }
#else
	inline constexpr DymanicModInt inv()const { return qpow(P - 2); }
	inline constexpr friend DymanicModInt inv(const DymanicModInt &x) { return x.inv(); }
#endif
	inline friend istream &operator>>(istream &is, DymanicModInt &x) { S y; is >> y, x = y; return is; }
	inline friend ostream &operator<<(ostream &os, const DymanicModInt &x) { return os << x.val(); }
#ifdef USE_FastIO
	inline void read() & { S x; ::read(x), *this = x; }
	inline void write()const { ::write(val()); }
#endif
};
template < class S, int ID > DymanicModInt < S, ID >::U DymanicModInt < S, ID >::P = 1;
template < class S, int ID > DymanicModInt < S, ID >::U DymanicModInt < S, ID >::P2 = 2;
template < class S, int ID > DymanicModInt < S, ID >::U DymanicModInt < S, ID >::R = -1;
template < class S, int ID > DymanicModInt < S, ID >::U DymanicModInt < S, ID >::R2 = 0;
using MI = DymanicModInt<int, 0>;

void init(int p){
	MI::set_mod(p);
}

int inv(int x){
	return MI(x).inv().val();
}