結果
問題 | No.2181 LRM Question 2 |
ユーザー |
|
提出日時 | 2023-01-06 21:42:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 23,745 bytes |
コンパイル時間 | 2,443 ms |
コンパイル使用メモリ | 271,272 KB |
最終ジャッジ日時 | 2025-02-09 23:47:21 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
/*** date : 2023-01-06 21:42:40*/#define NDEBUGusing namespace std;// intrinstic#include <immintrin.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cfenv>#include <cfloat>#include <chrono>#include <cinttypes>#include <climits>#include <cmath>#include <complex>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <initializer_list>#include <iomanip>#include <ios>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <streambuf>#include <string>#include <tuple>#include <type_traits>#include <typeinfo>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>// utilitynamespace Nyaan {using ll = long long;using i64 = long long;using u64 = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;template <typename T>using V = vector<T>;template <typename T>using VV = vector<vector<T>>;using vi = vector<int>;using vl = vector<long long>;using vd = V<double>;using vs = V<string>;using vvi = vector<vector<int>>;using vvl = vector<vector<long long>>;template <typename T, typename U>struct P : pair<T, U> {template <typename... Args>P(Args... args) : pair<T, U>(args...) {}using pair<T, U>::first;using pair<T, U>::second;P &operator+=(const P &r) {first += r.first;second += r.second;return *this;}P &operator-=(const P &r) {first -= r.first;second -= r.second;return *this;}P &operator*=(const P &r) {first *= r.first;second *= r.second;return *this;}template <typename S>P &operator*=(const S &r) {first *= r, second *= r;return *this;}P operator+(const P &r) const { return P(*this) += r; }P operator-(const P &r) const { return P(*this) -= r; }P operator*(const P &r) const { return P(*this) *= r; }template <typename S>P operator*(const S &r) const {return P(*this) *= r;}P operator-() const { return P{-first, -second}; }};using pl = P<ll, ll>;using pi = P<int, int>;using vp = V<pl>;constexpr int inf = 1001001001;constexpr long long infLL = 4004004004004004004LL;template <typename T>int sz(const T &t) {return t.size();}template <typename T, typename U>inline bool amin(T &x, U y) {return (y < x) ? (x = y, true) : false;}template <typename T, typename U>inline bool amax(T &x, U y) {return (x < y) ? (x = y, true) : false;}template <typename T>inline T Max(const vector<T> &v) {return *max_element(begin(v), end(v));}template <typename T>inline T Min(const vector<T> &v) {return *min_element(begin(v), end(v));}template <typename T>inline long long Sum(const vector<T> &v) {return accumulate(begin(v), end(v), 0LL);}template <typename T>int lb(const vector<T> &v, const T &a) {return lower_bound(begin(v), end(v), a) - begin(v);}template <typename T>int ub(const vector<T> &v, const T &a) {return upper_bound(begin(v), end(v), a) - begin(v);}constexpr long long TEN(int n) {long long ret = 1, x = 10;for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);return ret;}template <typename T, typename U>pair<T, U> mkp(const T &t, const U &u) {return make_pair(t, u);}template <typename T>vector<T> mkrui(const vector<T> &v, bool rev = false) {vector<T> ret(v.size() + 1);if (rev) {for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];} else {for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];}return ret;};template <typename T>vector<T> mkuni(const vector<T> &v) {vector<T> ret(v);sort(ret.begin(), ret.end());ret.erase(unique(ret.begin(), ret.end()), ret.end());return ret;}template <typename F>vector<int> mkord(int N,F f) {vector<int> ord(N);iota(begin(ord), end(ord), 0);sort(begin(ord), end(ord), f);return ord;}template <typename T>vector<int> mkinv(vector<T> &v) {int max_val = *max_element(begin(v), end(v));vector<int> inv(max_val + 1, -1);for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;return inv;}vector<int> mkiota(int n) {vector<int> ret(n);iota(begin(ret), end(ret), 0);return ret;}template <typename T>T mkrev(const T &v) {T w{v};reverse(begin(w), end(w));return w;}template <typename T>bool nxp(vector<T> &v) {return next_permutation(begin(v), end(v));}template <typename T>using minpq = priority_queue<T, vector<T>, greater<T>>;} // namespace Nyaan// bit operationnamespace Nyaan {__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {return _mm_popcnt_u64(a);}inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }template <typename T>inline int gbit(const T &a, int i) {return (a >> i) & 1;}template <typename T>inline void sbit(T &a, int i, bool b) {if (gbit(a, i) != b) a ^= T(1) << i;}constexpr long long PW(int n) { return 1LL << n; }constexpr long long MSK(int n) { return (1LL << n) - 1; }} // namespace Nyaan// inoutnamespace Nyaan {template <typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &p) {os << p.first << " " << p.second;return os;}template <typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p) {is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &v) {int s = (int)v.size();for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v) {for (auto &x : v) is >> x;return is;}istream &operator>>(istream &is, __int128_t &x) {string S;is >> S;x = 0;int flag = 0;for (auto &c : S) {if (c == '-') {flag = true;continue;}x *= 10;x += c - '0';}if (flag) x = -x;return is;}istream &operator>>(istream &is, __uint128_t &x) {string S;is >> S;x = 0;for (auto &c : S) {x *= 10;x += c - '0';}return is;}ostream &operator<<(ostream &os, __int128_t x) {if (x == 0) return os << 0;if (x < 0) os << '-', x = -x;string S;while (x) S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}ostream &operator<<(ostream &os, __uint128_t x) {if (x == 0) return os << 0;string S;while (x) S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}void in() {}template <typename T, class... U>void in(T &t, U &...u) {cin >> t;in(u...);}void out() { cout << "\n"; }template <typename T, class... U, char sep = ' '>void out(const T &t, const U &...u) {cout << t;if (sizeof...(u)) cout << sep;out(u...);}void outr() {}template <typename T, class... U, char sep = ' '>void outr(const T &t, const U &...u) {cout << t;outr(u...);}struct IoSetupNya {IoSetupNya() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(15);cerr << fixed << setprecision(7);}} iosetupnya;} // namespace Nyaan// debug#ifdef NyaanDebug#define trc(...) (void(0))#else#define trc(...) (void(0))#endif#ifdef NyaanLocal#define trc2(...) (void(0))#else#define trc2(...) (void(0))#endif// macro#define each(x, v) for (auto&& x : v)#define each2(x, y, v) for (auto&& [x, y] : v)#define all(v) (v).begin(), (v).end()#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)#define reg(i, a, b) for (long long i = (a); i < (b); i++)#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)#define fi first#define se second#define ini(...) \int __VA_ARGS__; \in(__VA_ARGS__)#define inl(...) \long long __VA_ARGS__; \in(__VA_ARGS__)#define ins(...) \string __VA_ARGS__; \in(__VA_ARGS__)#define in2(s, t) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i]); \}#define in3(s, t, u) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i]); \}#define in4(s, t, u, v) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i], v[i]); \}#define die(...) \do { \Nyaan::out(__VA_ARGS__); \return; \} while (0)namespace Nyaan {void solve();}int main() { Nyaan::solve(); }//using namespace std;struct Barrett {using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;u32 m;u64 im;Barrett() : m(), im() {}Barrett(int n) : m(n), im(u64(-1) / m + 1) {}constexpr inline i64 quo(u64 n) {u64 x = u64((__uint128_t(n) * im) >> 64);u32 r = n - x * m;return m <= r ? x - 1 : x;}constexpr inline i64 rem(u64 n) {u64 x = u64((__uint128_t(n) * im) >> 64);u32 r = n - x * m;return m <= r ? r + m : r;}constexpr inline pair<i64, int> quorem(u64 n) {u64 x = u64((__uint128_t(n) * im) >> 64);u32 r = n - x * m;if (m <= r) return {x - 1, r + m};return {x, r};}constexpr inline i64 pow(u64 n, i64 p) {u32 a = rem(n), r = m == 1 ? 0 : 1;while (p) {if (p & 1) r = rem(u64(r) * a);a = rem(u64(a) * a);p >>= 1;}return r;}};struct ArbitraryModInt {int x;ArbitraryModInt() : x(0) {}ArbitraryModInt(int64_t y) {int z = y % get_mod();if (z < 0) z += get_mod();x = z;}ArbitraryModInt &operator+=(const ArbitraryModInt &p) {if ((x += p.x) >= get_mod()) x -= get_mod();return *this;}ArbitraryModInt &operator-=(const ArbitraryModInt &p) {if ((x += get_mod() - p.x) >= get_mod()) x -= get_mod();return *this;}ArbitraryModInt &operator*=(const ArbitraryModInt &p) {x = rem((unsigned long long)x * p.x);return *this;}ArbitraryModInt &operator/=(const ArbitraryModInt &p) {*this *= p.inverse();return *this;}ArbitraryModInt operator-() const { return ArbitraryModInt(-x); }ArbitraryModInt operator+(const ArbitraryModInt &p) const {return ArbitraryModInt(*this) += p;}ArbitraryModInt operator-(const ArbitraryModInt &p) const {return ArbitraryModInt(*this) -= p;}ArbitraryModInt operator*(const ArbitraryModInt &p) const {return ArbitraryModInt(*this) *= p;}ArbitraryModInt operator/(const ArbitraryModInt &p) const {return ArbitraryModInt(*this) /= p;}bool operator==(const ArbitraryModInt &p) const { return x == p.x; }bool operator!=(const ArbitraryModInt &p) const { return x != p.x; }ArbitraryModInt inverse() const {int a = x, b = get_mod(), u = 1, v = 0, t;while (b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ArbitraryModInt(u);}ArbitraryModInt pow(int64_t n) const {ArbitraryModInt ret(1), mul(x);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ArbitraryModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ArbitraryModInt &a) {int64_t t;is >> t;a = ArbitraryModInt(t);return (is);}int get() const { return x; }inline unsigned int rem(unsigned long long p) { return barrett().rem(p); }static inline Barrett &barrett() {static Barrett b;return b;}static inline int &get_mod() {static int mod = 0;return mod;}static void set_mod(int md) {assert(0 < md && md <= (1LL << 30) - 1);get_mod() = md;barrett() = Barrett(md);}};//#ifdef _MSC_VER#include <intrin.h>#endifnamespace atcoder {namespace internal {// @param m `1 <= m`// @return x mod mconstexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0) x += m;return x;}// Fast modular multiplication by barrett reduction// Reference: https://en.wikipedia.org/wiki/Barrett_reduction// NOTE: reconsider after Ice Lakestruct barrett {unsigned int _m;unsigned long long im;// @param m `1 <= m < 2^31`barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}// @return munsigned int umod() const { return _m; }// @param a `0 <= a < m`// @param b `0 <= b < m`// @return `a * b % m`unsigned int mul(unsigned int a, unsigned int b) const {// [1] m = 1// a = b = im = 0, so okay// [2] m >= 2// im = ceil(2^64 / m)// -> im * m = 2^64 + r (0 <= r < m)// let z = a*b = c*m + d (0 <= c, d < m)// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2// ((ab * im) >> 64) == c or c + 1unsigned long long z = a;z *= b;#ifdef _MSC_VERunsigned long long x;_umul128(z, im, &x);#elseunsigned long long x =(unsigned long long)(((unsigned __int128)(z)*im) >> 64);#endifunsigned int v = (unsigned int)(z - x * _m);if (_m <= v) v += _m;return v;}};// @param n `0 <= n`// @param m `1 <= m`// @return `(x ** n) % m`constexpr long long pow_mod_constexpr(long long x, long long n, int m) {if (m == 1) return 0;unsigned int _m = (unsigned int)(m);unsigned long long r = 1;unsigned long long y = safe_mod(x, m);while (n) {if (n & 1) r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}// Reference:// M. Forisek and J. Jancina,// Fast Primality Testing for Integers That Fit into a Machine Word// @param n `0 <= n`constexpr bool is_prime_constexpr(int n) {if (n <= 1) return false;if (n == 2 || n == 7 || n == 61) return true;if (n % 2 == 0) return false;long long d = n - 1;while (d % 2 == 0) d /= 2;constexpr long long bases[3] = {2, 7, 61};for (long long a : bases) {long long t = d;long long y = pow_mod_constexpr(a, t, n);while (t != n - 1 && y != 1 && y != n - 1) {y = y * y % n;t <<= 1;}if (y != n - 1 && t % 2 == 0) {return false;}}return true;}template <int n> constexpr bool is_prime = is_prime_constexpr(n);// @param b `1 <= b`// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/gconstexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {a = safe_mod(a, b);if (a == 0) return {b, 0};// Contracts:// [1] s - m0 * a = 0 (mod b)// [2] t - m1 * a = 0 (mod b)// [3] s * |m1| + t * |m0| <= blong long s = b, t = a;long long m0 = 0, m1 = 1;while (t) {long long u = s / t;s -= t * u;m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b// [3]:// (s - t * u) * |m1| + t * |m0 - m1 * u|// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)// = s * |m1| + t * |m0| <= bauto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}// by [3]: |m0| <= b/g// by g != b: |m0| < b/gif (m0 < 0) m0 += b / s;return {s, m0};}// Compile time primitive root// @param m must be prime// @return primitive root (and minimum in now)constexpr int primitive_root_constexpr(int m) {if (m == 2) return 1;if (m == 167772161) return 3;if (m == 469762049) return 3;if (m == 754974721) return 11;if (m == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (long long)(i)*i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) {x /= i;}}}if (x > 1) {divs[cnt++] = x;}for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok) return g;}}template <int m> constexpr int primitive_root = primitive_root_constexpr(m);} // namespace internal} // namespace atcodernamespace atcoder {long long pow_mod(long long x, long long n, int m) {assert(0 <= n && 1 <= m);if (m == 1) return 0;internal::barrett bt((unsigned int)(m));unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));while (n) {if (n & 1) r = bt.mul(r, y);y = bt.mul(y, y);n >>= 1;}return r;}long long inv_mod(long long x, long long m) {assert(1 <= m);auto z = internal::inv_gcd(x, m);assert(z.first == 1);return z.second;}// (rem, mod)std::pair<long long, long long> crt(const std::vector<long long>& r,const std::vector<long long>& m) {assert(r.size() == m.size());int n = int(r.size());// Contracts: 0 <= r0 < m0long long r0 = 0, m0 = 1;for (int i = 0; i < n; i++) {assert(1 <= m[i]);long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];if (m0 < m1) {std::swap(r0, r1);std::swap(m0, m1);}if (m0 % m1 == 0) {if (r0 % m1 != r1) return {0, 0};continue;}// assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)// (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));// r2 % m0 = r0// r2 % m1 = r1// -> (r0 + x*m0) % m1 = r1// -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)// -> x = (r1 - r0) / g * inv(u0) (mod u1)// im = inv(u0) (mod u1) (0 <= im < u1)long long g, im;std::tie(g, im) = internal::inv_gcd(m0, m1);long long u1 = (m1 / g);// |r1 - r0| < (m0 + m1) <= lcm(m0, m1)if ((r1 - r0) % g) return {0, 0};// u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)long long x = (r1 - r0) / g % u1 * im % u1;// |r0| + |m0 * x|// < m0 + m0 * (u1 - 1)// = m0 + m0 * m1 / g - m0// = lcm(m0, m1)r0 += x * m0;m0 *= u1; // -> lcm(m0, m1)if (r0 < 0) r0 += m0;}return {r0, m0};}long long cnt = 0;long long floor_sum(long long n, long long m, long long a, long long b) {cnt++;long long ans = 0;if (a >= m) {ans += (n - 1) * n * (a / m) / 2;a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}long long y_max = (a * n + b) / m, x_max = (y_max * m - b);if (y_max == 0) return ans;ans += (n - (x_max + a - 1) / a) * y_max;ans += floor_sum(y_max, a, m, (a - x_max % a) % a);return ans;}} // namespace atcoderusing namespace std;#define PRIME_POWER_BINOMIAL_M_MAX ((1LL << 30) - 1)#define PRIME_POWER_BINOMIAL_N_MAX 20000000struct prime_power_binomial {int p, q, M;vector<int> fac, ifac, inv;int delta;Barrett bm, bp;prime_power_binomial(int _p, int _q) : p(_p), q(_q) {assert(1 < p && p <= PRIME_POWER_BINOMIAL_M_MAX);assert(_q > 0);long long m = 1;while (_q--) {m *= p;assert(m <= PRIME_POWER_BINOMIAL_M_MAX);}M = m;bm = Barrett(M), bp = Barrett(p);enumerate();delta = (p == 2 && q >= 3) ? 1 : M - 1;}void enumerate() {int MX = min<int>(M, PRIME_POWER_BINOMIAL_N_MAX + 10);fac.resize(MX);ifac.resize(MX);inv.resize(MX);fac[0] = ifac[0] = inv[0] = 1;fac[1] = ifac[1] = inv[1] = 1;for (int i = 2; i < MX; i++) {if (i % p == 0) {fac[i] = fac[i - 1];fac[i + 1] = bm.rem(1LL * fac[i - 1] * (i + 1));i++;} else {fac[i] = bm.rem(1LL * fac[i - 1] * i);}}ifac[MX - 1] = bm.pow(fac[MX - 1], M / p * (p - 1) - 1);for (int i = MX - 2; i > 1; --i) {if (i % p == 0) {ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));ifac[i - 1] = ifac[i];i--;} else {ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));}}}long long Lucas(long long n, long long m) {int res = 1;while (n) {int n0, m0;tie(n, n0) = bp.quorem(n);tie(m, m0) = bp.quorem(m);if (n0 < m0) return 0;res = bm.rem(1LL * res * fac[n0]);int buf = bm.rem(1LL * ifac[n0 - m0] * ifac[m0]);res = bm.rem(1LL * res * buf);}return res;}long long C(long long n, long long m) {if (n < m || n < 0 || m < 0) return 0;if (q == 1) return Lucas(n, m);long long r = n - m;int e0 = 0, eq = 0, i = 0;int res = 1;while (n) {res = bm.rem(1LL * res * fac[bm.rem(n)]);res = bm.rem(1LL * res * ifac[bm.rem(m)]);res = bm.rem(1LL * res * ifac[bm.rem(r)]);n = bp.quo(n);m = bp.quo(m);r = bp.quo(r);int eps = n - m - r;e0 += eps;if (e0 >= q) return 0;if (++i >= q) eq += eps;}if (eq & 1) res = bm.rem(1LL * res * delta);res = bm.rem(1LL * res * bm.pow(p, e0));return res;}};// constraints:// (M <= 1e7 and max(N) <= 1e18) or (M < 2^30 and max(N) <= 2e7)struct arbitrary_mod_binomial {int mod;vector<int> M;vector<prime_power_binomial> cs;arbitrary_mod_binomial(long long md) : mod(md) {assert(1 <= md);assert(md <= PRIME_POWER_BINOMIAL_M_MAX);for (int i = 2; i * i <= md; i++) {if (md % i == 0) {int j = 0, k = 1;while (md % i == 0) md /= i, j++, k *= i;M.push_back(k);cs.emplace_back(i, j);assert(M.back() == cs.back().M);}}if (md != 1) {M.push_back(md);cs.emplace_back(md, 1);}assert(M.size() == cs.size());}long long C(long long n, long long m) {if (mod == 1) return 0;vector<long long> rem, d;for (int i = 0; i < (int)cs.size(); i++) {rem.push_back(cs[i].C(n, m));d.push_back(M[i]);}return atcoder::crt(rem, d).first;}};#undef PRIME_POWER_BINOMIAL_M_MAX#undef PRIME_POWER_BINOMIAL_N_MAX/*** @brief 任意mod二項係数* @docs docs/modulo/arbitrary-mod-binomial.md*/using mint = ArbitraryModInt;using namespace Nyaan;/*// sum [1, N]mint calc(ll N, ll M) {// n^2 * 2^2 * 3^2 * ... * n^2// n^2 * (n-1)^2 * 3^2 * ... * n^2// ...// n^2 * (n-1)^2 * (n-2)^2 * ... * n^2// = (n!)^2 / (1!)^2 (n-1)!^2 + ...// = binom(2n, n) - 2// (n!)^2 で割って// (binom(2n, n) - 2) / (n!)^2}*/void q() {/*mint::set_mod(998244353);Binomial<mint> C;reg(n, 2, 10) {mint x = C(2 * n, n) - 2;trc(n, x);}*/inl(L, R, M);arbitrary_mod_binomial C{M};ll ans = 0;reg(n, L, R + 1) {ans += C.C(2 * n, n);ans += M - 2;ans %= M;}out(ans);}void Nyaan::solve() {int t = 1;// in(t);while (t--) q();}