1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| typedef long long LL;
const int Mod = 998244353;
struct FastMod
{
typedef unsigned long long ULL;
typedef unsigned __int128 UL;
bool flag;
int d, l; ULL m;
FastMod () {}
FastMod (int _d) : d(_d)
{
l = 64 - __builtin_clzll(d - 1);
const UL i = 1;
UL M = ((i << (64 + l)) + (i << l)) / d;
if (M < (i << 64)) flag = 1, m = M;
else flag = 0, m = M - (i << 64);
}
friend ULL operator/(ULL n, const FastMod &m)
{
if (m.flag) return (UL)n * m.m >> 64 >> m.l;
ULL t = (UL)n * m.m >> 64;
return (((n - t) >> 1) + t) >> (m.l - 1);
}
template <class Type>
friend Type operator % (Type n, const FastMod &m)
{
bool flag = false;
if (n < 0) flag = true, n = ~n + 1;
n -= n / m * m.d;
if (flag) n = ~n + 1;
return n;
}
} mod(Mod);
void adj (int &x) { x += x >> 31 & Mod; }
int binpow (int b, LL k = Mod - 2)
{
int res = 1;
for (; k; k >>= 1, b = (LL)b * b % mod)
if (k & 1) res = (LL)res * b % mod;
return res;
}
struct ModInt
{
int x;
ModInt (int _ = 0) { adj(x = _); }
int operator () () const { return x; }
ModInt& operator += (const ModInt &_) { adj(x += _.x - Mod); return *this; }
ModInt& operator -= (const ModInt &_) { adj(x -= _.x); return *this; }
ModInt& operator *= (const ModInt &_) { x = (LL)x * _.x % mod; return *this; }
ModInt& operator /= (const ModInt &_) { x = (LL)x * binpow(_.x) % mod; return *this; }
ModInt& operator ^= (const LL &_) { x = binpow(x, _); return *this; }
ModInt operator - () const { return ModInt(-x); }
ModInt operator + (const ModInt &_) const { ModInt res = x; res += _; return res; }
ModInt operator - (const ModInt &_) const { ModInt res = x; res -= _; return res; }
ModInt operator * (const ModInt &_) const { ModInt res = x; res *= _; return res; }
ModInt operator / (const ModInt &_) const { ModInt res = x; res /= _; return res; }
ModInt operator ^ (const LL &_) const { ModInt res = x; res ^= _; return res; }
};
|