結果
| 問題 | No.2181 LRM Question 2 |
| ユーザー |
 NyaanNyaan
|
| 提出日時 | 2023-01-06 21:42:46 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 92 ms / 2,000 ms |
| コード長 | 23,745 bytes |
| コンパイル時間 | 3,944 ms |
| コンパイル使用メモリ | 266,232 KB |
| 実行使用メモリ | 13,556 KB |
| 最終ジャッジ日時 | 2023-08-20 14:46:46 |
| 合計ジャッジ時間 | 5,332 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 55 ms
4,380 KB |
| testcase_03 | AC | 1 ms
4,376 KB |
| testcase_04 | AC | 2 ms
4,380 KB |
| testcase_05 | AC | 2 ms
4,380 KB |
| testcase_06 | AC | 2 ms
4,376 KB |
| testcase_07 | AC | 1 ms
4,380 KB |
| testcase_08 | AC | 80 ms
4,380 KB |
| testcase_09 | AC | 56 ms
4,380 KB |
| testcase_10 | AC | 88 ms
4,384 KB |
| testcase_11 | AC | 92 ms
4,376 KB |
| testcase_12 | AC | 84 ms
4,384 KB |
| testcase_13 | AC | 2 ms
4,380 KB |
| testcase_14 | AC | 18 ms
13,556 KB |
| testcase_15 | AC | 3 ms
4,376 KB |
| testcase_16 | AC | 16 ms
11,116 KB |
| testcase_17 | AC | 2 ms
4,380 KB |
| testcase_18 | AC | 2 ms
4,384 KB |
| testcase_19 | AC | 2 ms
4,380 KB |
| testcase_20 | AC | 6 ms
5,776 KB |
| testcase_21 | AC | 12 ms
4,376 KB |
| testcase_22 | AC | 2 ms
4,376 KB |
| testcase_23 | AC | 2 ms
4,376 KB |
| testcase_24 | AC | 1 ms
4,376 KB |
| testcase_25 | AC | 2 ms
4,384 KB |
ソースコード
/**
* date : 2023-01-06 21:42:40
*/
#define NDEBUG
using 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>
// utility
namespace 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 operation
namespace 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
// inout
namespace 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>
#endif
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr 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 Lake
struct 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 m
unsigned 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 + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned 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/g
constexpr 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| <= b
long 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| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (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 atcoder
namespace 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 < m0
long 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 atcoder
using namespace std;
#define PRIME_POWER_BINOMIAL_M_MAX ((1LL << 30) - 1)
#define PRIME_POWER_BINOMIAL_N_MAX 20000000
struct 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();
}