proconlib
This documentation is automatically generated by competitive-verifier/competitive-verifier
tests/monoids.test.cpp
- View this file on GitHub
- Last update: 2026-02-21 18:33:47+09:00
Depends on
- std::abs(x) extended for my library (tools/abs.hpp)
- Concept for arithmetic types including tools::int128_t and tools::uint128_t (tools/arithmetic.hpp)
- Assertion macro (tools/assert_that.hpp)
- Arbitrary precision integer (tools/bigint.hpp)
- $2^{\left\lceil \log_2(x) \right\rceil}$ (tools/bit_ceil.hpp)
- $2^{\left\lfloor \log_2(x) \right\rfloor}$ (tools/bit_floor.hpp)
- Bit width required to represent a given integer (tools/bit_width.hpp)
- $\left\lceil \frac{x}{y} \right\rceil y$ (tools/block_ceil.hpp)
- $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
- chmin function (tools/chmin.hpp)
- std::cmp_less extended for my library (tools/cmp_less.hpp)
- Number of trailing zeros (tools/countr_zero.hpp)
- tools/detail/int128_t_and_uint128_t.hpp
- Extended Euclidean algorithm (tools/extgcd.hpp)
- $\left\lfloor \frac{x}{y} \right\rfloor$ (tools/floor.hpp)
- $\left\lfloor \log_2(x) \right\rfloor$ (tools/floor_log2.hpp)
- Garner's algorithm for $\mathbb{Z} / M_1 \mathbb{Z}$ and $\mathbb{Z} / M_2 \mathbb{Z}$ (tools/garner2.hpp)
- std::gcd(m, n) extended for my library (tools/gcd.hpp)
- Check whether a given integer is $2^n$ (tools/has_single_bit.hpp)
- Combine hash values (tools/hash_combine.hpp)
- 128-bit signed integer (tools/int128_t.hpp)
- Concept for integral types including tools::int128_t and tools::uint128_t (tools/integral.hpp)
- std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
- Miller-Rabin primality test (tools/is_prime.hpp)
- std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
- std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
- std::make_signed extended for tools::int128_t and tools::uint128_t (tools/make_signed.hpp)
- std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
- Minimum non-negative reminder (tools/mod.hpp)
- Typical monoids (tools/monoids.hpp)
- Concept for a mutable type (tools/mutable_type.hpp)
- tools::integral except for bool (tools/non_bool_integral.hpp)
- The number of nanoseconds that have elapsed since epoch (tools/now.hpp)
- Popcount (tools/popcount.hpp)
- $2^x$ (tools/pow2.hpp)
- $x^y \pmod{M}$ (tools/pow_mod.hpp)
- $x \cdot y \pmod{M}$ (tools/prod_mod.hpp)
- Quotient as integer division (tools/quo.hpp)
- Concept for signed integral types including tools::int128_t (tools/signed_integral.hpp)
- Sign function (tools/signum.hpp)
- 128-bit unsigned integer (tools/uint128_t.hpp)
- Concept for unsigned integral types including tools::uint128_t (tools/unsigned_integral.hpp)
Code
// competitive-verifier: STANDALONE
#include <iostream>
#include <limits>
#include "atcoder/modint.hpp"
#include "tools/assert_that.hpp"
#include "tools/bigint.hpp"
#include "tools/int128_t.hpp"
#include "tools/monoids.hpp"
#include "tools/uint128_t.hpp"
using mint = atcoder::modint998244353;
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
assert_that(tools::monoids::bit_and<bool>::op(false, true) == false);
assert_that(tools::monoids::bit_and<bool>::e() == true);
assert_that(tools::monoids::bit_and<short>::op(3, 5) == 1);
assert_that(tools::monoids::bit_and<short>::e() == std::numeric_limits<short>::max());
assert_that(tools::monoids::bit_and<unsigned short>::op(3U, 5U) == 1U);
assert_that(tools::monoids::bit_and<unsigned short>::e() == std::numeric_limits<unsigned short>::max());
assert_that(tools::monoids::bit_and<int>::op(3, 5) == 1);
assert_that(tools::monoids::bit_and<int>::e() == std::numeric_limits<int>::max());
assert_that(tools::monoids::bit_and<unsigned int>::op(3U, 5U) == 1U);
assert_that(tools::monoids::bit_and<unsigned int>::e() == std::numeric_limits<unsigned int>::max());
assert_that(tools::monoids::bit_and<long>::op(3L, 5L) == 1L);
assert_that(tools::monoids::bit_and<long>::e() == std::numeric_limits<long>::max());
assert_that(tools::monoids::bit_and<unsigned long>::op(3UL, 5UL) == 1UL);
assert_that(tools::monoids::bit_and<unsigned long>::e() == std::numeric_limits<unsigned long>::max());
assert_that(tools::monoids::bit_and<long long>::op(3LL, 5LL) == 1LL);
assert_that(tools::monoids::bit_and<long long>::e() == std::numeric_limits<long long>::max());
assert_that(tools::monoids::bit_and<unsigned long long>::op(3ULL, 5ULL) == 1ULL);
assert_that(tools::monoids::bit_and<unsigned long long>::e() == std::numeric_limits<unsigned long long>::max());
assert_that(tools::monoids::bit_and<tools::int128_t>::op(INT128_C(3), INT128_C(5)) == INT128_C(1));
assert_that(tools::monoids::bit_and<tools::int128_t>::e() == std::numeric_limits<tools::int128_t>::max());
assert_that(tools::monoids::bit_and<tools::uint128_t>::op(UINT128_C(3), UINT128_C(5)) == UINT128_C(1));
assert_that(tools::monoids::bit_and<tools::uint128_t>::e() == std::numeric_limits<tools::uint128_t>::max());
assert_that(tools::monoids::bit_or<bool>::op(false, true) == true);
assert_that(tools::monoids::bit_or<bool>::e() == false);
assert_that(tools::monoids::bit_or<short>::op(3, 5) == 7);
assert_that(tools::monoids::bit_or<short>::e() == 0);
assert_that(tools::monoids::bit_or<unsigned short>::op(3U, 5U) == 7U);
assert_that(tools::monoids::bit_or<unsigned short>::e() == 0U);
assert_that(tools::monoids::bit_or<int>::op(3, 5) == 7);
assert_that(tools::monoids::bit_or<int>::e() == 0);
assert_that(tools::monoids::bit_or<unsigned int>::op(3U, 5U) == 7U);
assert_that(tools::monoids::bit_or<unsigned int>::e() == 0U);
assert_that(tools::monoids::bit_or<long>::op(3L, 5L) == 7L);
assert_that(tools::monoids::bit_or<long>::e() == 0L);
assert_that(tools::monoids::bit_or<unsigned long>::op(3UL, 5UL) == 7UL);
assert_that(tools::monoids::bit_or<unsigned long>::e() == 0UL);
assert_that(tools::monoids::bit_or<long long>::op(3LL, 5LL) == 7LL);
assert_that(tools::monoids::bit_or<long long>::e() == 0LL);
assert_that(tools::monoids::bit_or<unsigned long long>::op(3ULL, 5ULL) == 7ULL);
assert_that(tools::monoids::bit_or<unsigned long long>::e() == 0ULL);
assert_that(tools::monoids::bit_or<tools::int128_t>::op(INT128_C(3), INT128_C(5)) == INT128_C(7));
assert_that(tools::monoids::bit_or<tools::int128_t>::e() == INT128_C(0));
assert_that(tools::monoids::bit_or<tools::uint128_t>::op(UINT128_C(3), UINT128_C(5)) == UINT128_C(7));
assert_that(tools::monoids::bit_or<tools::uint128_t>::e() == UINT128_C(0));
assert_that(tools::monoids::gcd<short>::op(-12, 18) == 6);
assert_that(tools::monoids::gcd<short>::e() == 0);
assert_that(tools::monoids::gcd<unsigned short>::op(12U, 18U) == 6U);
assert_that(tools::monoids::gcd<unsigned short>::e() == 0U);
assert_that(tools::monoids::gcd<int>::op(-12, 18) == 6);
assert_that(tools::monoids::gcd<int>::e() == 0);
assert_that(tools::monoids::gcd<unsigned int>::op(12U, 18U) == 6U);
assert_that(tools::monoids::gcd<unsigned int>::e() == 0U);
assert_that(tools::monoids::gcd<long>::op(-12L, 18L) == 6L);
assert_that(tools::monoids::gcd<long>::e() == 0L);
assert_that(tools::monoids::gcd<unsigned long>::op(12UL, 18UL) == 6UL);
assert_that(tools::monoids::gcd<unsigned long>::e() == 0UL);
assert_that(tools::monoids::gcd<long long>::op(-12LL, 18LL) == 6LL);
assert_that(tools::monoids::gcd<long long>::e() == 0LL);
assert_that(tools::monoids::gcd<unsigned long long>::op(12ULL, 18ULL) == 6ULL);
assert_that(tools::monoids::gcd<unsigned long long>::e() == 0ULL);
assert_that(tools::monoids::gcd<tools::int128_t>::op(INT128_C(-12), INT128_C(18)) == INT128_C(6));
assert_that(tools::monoids::gcd<tools::int128_t>::e() == INT128_C(0));
assert_that(tools::monoids::gcd<tools::uint128_t>::op(UINT128_C(12), UINT128_C(18)) == UINT128_C(6));
assert_that(tools::monoids::gcd<tools::uint128_t>::e() == UINT128_C(0));
assert_that(tools::monoids::gcd<tools::bigint>::op(tools::bigint(-12), tools::bigint(18)) == tools::bigint(6));
assert_that(tools::monoids::gcd<tools::bigint>::e() == tools::bigint(0));
assert_that(tools::monoids::max<bool>::op(false, true) == true);
assert_that(tools::monoids::max<bool>::e() == false);
assert_that(tools::monoids::max<char>::op('a', 'b') == 'b');
assert_that(tools::monoids::max<char>::e() == std::numeric_limits<char>::min());
assert_that(tools::monoids::max<short>::op(-1, 1) == 1);
assert_that(tools::monoids::max<short>::e() == std::numeric_limits<short>::min());
assert_that(tools::monoids::max<unsigned short>::op(0U, 1U) == 1U);
assert_that(tools::monoids::max<unsigned short>::e() == 0U);
assert_that(tools::monoids::max<int>::op(-1, 1) == 1);
assert_that(tools::monoids::max<int>::e() == std::numeric_limits<int>::min());
assert_that(tools::monoids::max<unsigned int>::op(0U, 1U) == 1U);
assert_that(tools::monoids::max<unsigned int>::e() == 0U);
assert_that(tools::monoids::max<long>::op(-1L, 1L) == 1L);
assert_that(tools::monoids::max<long>::e() == std::numeric_limits<long>::min());
assert_that(tools::monoids::max<unsigned long>::op(0UL, 1UL) == 1UL);
assert_that(tools::monoids::max<unsigned long>::e() == 0UL);
assert_that(tools::monoids::max<long long>::op(-1LL, 1LL) == 1LL);
assert_that(tools::monoids::max<long long>::e() == std::numeric_limits<long long>::min());
assert_that(tools::monoids::max<unsigned long long>::op(0ULL, 1ULL) == 1ULL);
assert_that(tools::monoids::max<unsigned long long>::e() == 0ULL);
assert_that(tools::monoids::max<float>::op(-1.0F, 1.0F) == 1.0F);
assert_that(tools::monoids::max<float>::e() == -std::numeric_limits<float>::infinity());
assert_that(tools::monoids::max<double>::op(-1.0, 1.0) == 1.0);
assert_that(tools::monoids::max<double>::e() == -std::numeric_limits<double>::infinity());
assert_that(tools::monoids::max<long double>::op(-1.0L, 1.0L) == 1.0L);
assert_that(tools::monoids::max<long double>::e() == -std::numeric_limits<long double>::infinity());
assert_that(tools::monoids::max<tools::int128_t>::op(INT128_C(-1), INT128_C(1)) == INT128_C(1));
assert_that(tools::monoids::max<tools::int128_t>::e() == std::numeric_limits<tools::int128_t>::min());
assert_that(tools::monoids::max<tools::uint128_t>::op(UINT128_C(0), UINT128_C(1)) == UINT128_C(1));
assert_that(tools::monoids::max<tools::uint128_t>::e() == UINT128_C(0));
assert_that(tools::monoids::max<int, 42>::op(42, 43) == 43);
assert_that(tools::monoids::max<int, 42>::e() == 42);
assert_that(tools::monoids::min<bool>::op(false, true) == false);
assert_that(tools::monoids::min<bool>::e() == true);
assert_that(tools::monoids::min<char>::op('a', 'b') == 'a');
assert_that(tools::monoids::min<char>::e() == std::numeric_limits<char>::max());
assert_that(tools::monoids::min<short>::op(-1, 1) == -1);
assert_that(tools::monoids::min<short>::e() == std::numeric_limits<short>::max());
assert_that(tools::monoids::min<unsigned short>::op(0U, 1U) == 0U);
assert_that(tools::monoids::min<unsigned short>::e() == std::numeric_limits<unsigned short>::max());
assert_that(tools::monoids::min<int>::op(-1, 1) == -1);
assert_that(tools::monoids::min<int>::e() == std::numeric_limits<int>::max());
assert_that(tools::monoids::min<unsigned int>::op(0U, 1U) == 0U);
assert_that(tools::monoids::min<unsigned int>::e() == std::numeric_limits<unsigned int>::max());
assert_that(tools::monoids::min<long>::op(-1L, 1L) == -1L);
assert_that(tools::monoids::min<long>::e() == std::numeric_limits<long>::max());
assert_that(tools::monoids::min<unsigned long>::op(0UL, 1UL) == 0UL);
assert_that(tools::monoids::min<unsigned long>::e() == std::numeric_limits<unsigned long>::max());
assert_that(tools::monoids::min<long long>::op(-1LL, 1LL) == -1LL);
assert_that(tools::monoids::min<long long>::e() == std::numeric_limits<long long>::max());
assert_that(tools::monoids::min<unsigned long long>::op(0ULL, 1ULL) == 0ULL);
assert_that(tools::monoids::min<unsigned long long>::e() == std::numeric_limits<unsigned long long>::max());
assert_that(tools::monoids::min<float>::op(-1.0F, 1.0F) == -1.0F);
assert_that(tools::monoids::min<float>::e() == std::numeric_limits<float>::infinity());
assert_that(tools::monoids::min<double>::op(-1.0, 1.0) == -1.0);
assert_that(tools::monoids::min<double>::e() == std::numeric_limits<double>::infinity());
assert_that(tools::monoids::min<long double>::op(-1.0L, 1.0L) == -1.0L);
assert_that(tools::monoids::min<long double>::e() == std::numeric_limits<long double>::infinity());
assert_that(tools::monoids::min<tools::int128_t>::op(INT128_C(-1), INT128_C(1)) == INT128_C(-1));
assert_that(tools::monoids::min<tools::int128_t>::e() == std::numeric_limits<tools::int128_t>::max());
assert_that(tools::monoids::min<tools::uint128_t>::op(UINT128_C(0), UINT128_C(1)) == UINT128_C(0));
assert_that(tools::monoids::min<tools::uint128_t>::e() == std::numeric_limits<tools::uint128_t>::max());
assert_that(tools::monoids::min<int, 42>::op(41, 42) == 41);
assert_that(tools::monoids::min<int, 42>::e() == 42);
assert_that(tools::monoids::multiplies<bool>::op(false, true) == false);
assert_that(tools::monoids::multiplies<bool>::e() == true);
assert_that(tools::monoids::multiplies<short>::op(-2, 3) == -6);
assert_that(tools::monoids::multiplies<short>::e() == 1);
assert_that(tools::monoids::multiplies<unsigned short>::op(2U, 3U) == 6U);
assert_that(tools::monoids::multiplies<unsigned short>::e() == 1U);
assert_that(tools::monoids::multiplies<int>::op(-2, 3) == -6);
assert_that(tools::monoids::multiplies<int>::e() == 1);
assert_that(tools::monoids::multiplies<unsigned int>::op(2U, 3U) == 6U);
assert_that(tools::monoids::multiplies<unsigned int>::e() == 1U);
assert_that(tools::monoids::multiplies<long>::op(-2L, 3L) == -6L);
assert_that(tools::monoids::multiplies<long>::e() == 1L);
assert_that(tools::monoids::multiplies<unsigned long>::op(2UL, 3UL) == 6UL);
assert_that(tools::monoids::multiplies<unsigned long>::e() == 1UL);
assert_that(tools::monoids::multiplies<long long>::op(-2LL, 3LL) == -6LL);
assert_that(tools::monoids::multiplies<long long>::e() == 1LL);
assert_that(tools::monoids::multiplies<unsigned long long>::op(2ULL, 3ULL) == 6ULL);
assert_that(tools::monoids::multiplies<unsigned long long>::e() == 1ULL);
assert_that(tools::monoids::multiplies<float>::op(-2.0F, 3.0F) == -6.0F);
assert_that(tools::monoids::multiplies<float>::e() == 1.0F);
assert_that(tools::monoids::multiplies<double>::op(-2.0, 3.0) == -6.0);
assert_that(tools::monoids::multiplies<double>::e() == 1.0);
assert_that(tools::monoids::multiplies<long double>::op(-2.0L, 3.0L) == -6.0L);
assert_that(tools::monoids::multiplies<long double>::e() == 1.0L);
assert_that(tools::monoids::multiplies<mint>::op(mint::raw(2), mint::raw(3)) == mint::raw(6));
assert_that(tools::monoids::multiplies<mint>::e() == mint::raw(1));
assert_that(tools::monoids::multiplies<tools::int128_t>::op(INT128_C(-2), INT128_C(3)) == INT128_C(-6));
assert_that(tools::monoids::multiplies<tools::int128_t>::e() == INT128_C(1));
assert_that(tools::monoids::multiplies<tools::uint128_t>::op(UINT128_C(2), UINT128_C(3)) == UINT128_C(6));
assert_that(tools::monoids::multiplies<tools::uint128_t>::e() == UINT128_C(1));
assert_that(tools::monoids::multiplies<tools::bigint>::op(tools::bigint(-2), tools::bigint(3)) == tools::bigint(-6));
assert_that(tools::monoids::multiplies<tools::bigint>::e() == tools::bigint(1));
assert_that(tools::monoids::update<bool, false>::op(true, false) == true);
assert_that(tools::monoids::update<bool, false>::op(false, true) == true);
assert_that(tools::monoids::update<bool, false>::e() == false);
assert_that(tools::monoids::update<char, '\0'>::op('a', 'b') == 'a');
assert_that(tools::monoids::update<char, '\0'>::op('\0', 'b') == 'b');
assert_that(tools::monoids::update<char, '\0'>::e() == '\0');
assert_that(tools::monoids::update<short, 42>::op(-1, 1) == -1);
assert_that(tools::monoids::update<short, 42>::op(42, 1) == 1);
assert_that(tools::monoids::update<short, 42>::e() == 42);
assert_that(tools::monoids::update<unsigned short, 42U>::op(0U, 1U) == 0U);
assert_that(tools::monoids::update<unsigned short, 42U>::op(42U, 1U) == 1U);
assert_that(tools::monoids::update<unsigned short, 42U>::e() == 42U);
assert_that(tools::monoids::update<int, 42>::op(-1, 1) == -1);
assert_that(tools::monoids::update<int, 42>::op(42, 1) == 1);
assert_that(tools::monoids::update<int, 42>::e() == 42);
assert_that(tools::monoids::update<unsigned int, 42U>::op(0U, 1U) == 0U);
assert_that(tools::monoids::update<unsigned int, 42U>::op(42U, 1U) == 1U);
assert_that(tools::monoids::update<unsigned int, 42U>::e() == 42U);
assert_that(tools::monoids::update<long, 42L>::op(-1L, 1L) == -1L);
assert_that(tools::monoids::update<long, 42L>::op(42L, 1L) == 1L);
assert_that(tools::monoids::update<long, 42L>::e() == 42L);
assert_that(tools::monoids::update<unsigned long, 42UL>::op(0UL, 1UL) == 0UL);
assert_that(tools::monoids::update<unsigned long, 42UL>::op(42UL, 1UL) == 1UL);
assert_that(tools::monoids::update<unsigned long, 42UL>::e() == 42UL);
assert_that(tools::monoids::update<long long, 42LL>::op(-1LL, 1LL) == -1LL);
assert_that(tools::monoids::update<long long, 42LL>::op(42LL, 1LL) == 1LL);
assert_that(tools::monoids::update<long long, 42LL>::e() == 42LL);
assert_that(tools::monoids::update<unsigned long long, 42ULL>::op(0ULL, 1ULL) == 0ULL);
assert_that(tools::monoids::update<unsigned long long, 42ULL>::op(42ULL, 1ULL) == 1ULL);
assert_that(tools::monoids::update<unsigned long long, 42ULL>::e() == 42ULL);
assert_that(tools::monoids::update<tools::int128_t, INT128_C(42)>::op(INT128_C(-1), INT128_C(1)) == INT128_C(-1));
assert_that(tools::monoids::update<tools::int128_t, INT128_C(42)>::op(INT128_C(42), INT128_C(1)) == INT128_C(1));
assert_that(tools::monoids::update<tools::int128_t, INT128_C(42)>::e() == INT128_C(42));
assert_that(tools::monoids::update<tools::uint128_t, UINT128_C(42)>::op(UINT128_C(0), UINT128_C(1)) == UINT128_C(0));
assert_that(tools::monoids::update<tools::uint128_t, UINT128_C(42)>::op(UINT128_C(42), UINT128_C(1)) == UINT128_C(1));
assert_that(tools::monoids::update<tools::uint128_t, UINT128_C(42)>::e() == UINT128_C(42));
return 0;
}
#line 1 "tests/monoids.test.cpp"
// competitive-verifier: STANDALONE
#include <iostream>
#include <limits>
#line 1 "lib/ac-library/atcoder/modint.hpp"
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#line 1 "lib/ac-library/atcoder/internal_math.hpp"
#include <utility>
#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`
explicit 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 long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @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);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#line 1 "lib/ac-library/atcoder/internal_type_traits.hpp"
#line 7 "lib/ac-library/atcoder/internal_type_traits.hpp"
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#line 14 "lib/ac-library/atcoder/modint.hpp"
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
#line 1 "tools/assert_that.hpp"
#line 5 "tools/assert_that.hpp"
#include <cstdlib>
#define assert_that_impl(cond, file, line, func) do {\
if (!cond) {\
std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
std::exit(EXIT_FAILURE);\
}\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)
#line 1 "tools/bigint.hpp"
#include <algorithm>
#include <array>
#line 7 "tools/bigint.hpp"
#include <compare>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#line 12 "tools/bigint.hpp"
#include <iterator>
#line 14 "tools/bigint.hpp"
#include <memory>
#include <ranges>
#include <string>
#include <string_view>
#include <tuple>
#line 20 "tools/bigint.hpp"
#include <vector>
#line 1 "lib/ac-library/atcoder/convolution.hpp"
#line 9 "lib/ac-library/atcoder/convolution.hpp"
#line 1 "lib/ac-library/atcoder/internal_bit.hpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
#line 12 "lib/ac-library/atcoder/convolution.hpp"
namespace atcoder {
namespace internal {
template <class mint,
int g = internal::primitive_root<mint::mod()>,
internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
static constexpr int rank2 = countr_zero_constexpr(mint::mod() - 1);
std::array<mint, rank2 + 1> root; // root[i]^(2^i) == 1
std::array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1
std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;
std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;
std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;
std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;
fft_info() {
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
};
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
int n = int(a.size());
int h = internal::countr_zero((unsigned int)n);
static const fft_info<mint> info;
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len))
rot *= info.rate2[countr_zero(~(unsigned int)(s))];
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
mint rot = 1, imag = info.root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * mint::mod() * mint::mod();
auto a0 = 1ULL * a[i + offset].val();
auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
auto a1na3imag =
1ULL * mint(a1 + mod2 - a3).val() * imag.val();
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= info.rate3[countr_zero(~(unsigned int)(s))];
}
len += 2;
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
int n = int(a.size());
int h = internal::countr_zero((unsigned int)n);
static const fft_info<mint> info;
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)((unsigned int)(l.val() - r.val()) + mint::mod()) *
irot.val();
;
}
if (s + 1 != (1 << (len - 1)))
irot *= info.irate2[countr_zero(~(unsigned int)(s))];
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
mint irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].val();
auto a1 = 1ULL * a[i + offset + 1 * p].val();
auto a2 = 1ULL * a[i + offset + 2 * p].val();
auto a3 = 1ULL * a[i + offset + 3 * p].val();
auto a2na3iimag =
1ULL *
mint((mint::mod() + a2 - a3) * iimag.val()).val();
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] =
(a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
a[i + offset + 2 * p] =
(a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
irot2.val();
a[i + offset + 3 * p] =
(a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
irot3.val();
}
if (s + 1 != (1 << (len - 2)))
irot *= info.irate3[countr_zero(~(unsigned int)(s))];
}
len -= 2;
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_naive(const std::vector<mint>& a,
const std::vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
std::vector<mint> ans(n + m - 1);
if (n < m) {
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
ans[i + j] += a[i] * b[j];
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
}
return ans;
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
} // namespace internal
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
[[maybe_unused]] int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
if (std::min(n, m) <= 60) return convolution_naive(std::move(a), std::move(b));
return internal::convolution_fft(std::move(a), std::move(b));
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(const std::vector<mint>& a,
const std::vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
[[maybe_unused]] int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
if (std::min(n, m) <= 60) return convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <unsigned int mod = 998244353,
class T,
std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = static_modint<mod>;
[[maybe_unused]] int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
std::vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(std::move(a2), std::move(b2));
std::vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
std::vector<long long> convolution_ll(const std::vector<long long>& a,
const std::vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721; // 2^24
static constexpr unsigned long long MOD2 = 167772161; // 2^25
static constexpr unsigned long long MOD3 = 469762049; // 2^26
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
internal::inv_gcd(MOD1 * MOD2, MOD3).second;
static constexpr int MAX_AB_BIT = 24;
static_assert(MOD1 % (1ull << MAX_AB_BIT) == 1, "MOD1 isn't enough to support an array length of 2^24.");
static_assert(MOD2 % (1ull << MAX_AB_BIT) == 1, "MOD2 isn't enough to support an array length of 2^24.");
static_assert(MOD3 % (1ull << MAX_AB_BIT) == 1, "MOD3 isn't enough to support an array length of 2^24.");
assert(n + m - 1 <= (1 << MAX_AB_BIT));
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
std::vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
// B = 2^63, -B <= x, r(real value) < B
// (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
// r = c1[i] (mod MOD1)
// focus on MOD1
// r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
// r = x,
// x - M' + (0 or 2B),
// x - 2M' + (0, 2B or 4B),
// x - 3M' + (0, 2B, 4B or 6B) (without mod!)
// (r - x) = 0, (0)
// - M' + (0 or 2B), (1)
// -2M' + (0 or 2B or 4B), (2)
// -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
// we checked that
// ((1) mod MOD1) mod 5 = 2
// ((2) mod MOD1) mod 5 = 3
// ((3) mod MOD1) mod 5 = 4
long long diff =
c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
} // namespace atcoder
#line 1 "tools/abs.hpp"
#include <cmath>
#line 7 "tools/abs.hpp"
namespace tools {
namespace detail::abs {
template <typename T>
struct impl {
constexpr decltype(auto) operator()(const T x) const noexcept(noexcept(std::abs(x))) {
return std::abs(x);
}
};
}
template <typename T>
constexpr decltype(auto) abs(T&& x) noexcept(noexcept(tools::detail::abs::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::abs::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 1 "tools/block_ceil.hpp"
#line 1 "tools/ceil.hpp"
#line 1 "tools/non_bool_integral.hpp"
#include <concepts>
#line 1 "tools/integral.hpp"
#line 1 "tools/is_integral.hpp"
#line 5 "tools/is_integral.hpp"
namespace tools {
template <typename T>
struct is_integral : std::is_integral<T> {};
template <typename T>
inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}
#line 5 "tools/integral.hpp"
namespace tools {
template <typename T>
concept integral = tools::is_integral_v<T>;
}
#line 7 "tools/non_bool_integral.hpp"
namespace tools {
template <typename T>
concept non_bool_integral = tools::integral<T> && !std::same_as<std::remove_cv_t<T>, bool>;
}
#line 1 "tools/is_unsigned.hpp"
#line 5 "tools/is_unsigned.hpp"
namespace tools {
template <typename T>
struct is_unsigned : std::is_unsigned<T> {};
template <typename T>
inline constexpr bool is_unsigned_v = tools::is_unsigned<T>::value;
}
#line 8 "tools/ceil.hpp"
namespace tools {
template <tools::non_bool_integral M, tools::non_bool_integral N>
constexpr std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
assert(y != 0);
if (y >= 0) {
if (x > 0) {
return (x - 1) / y + 1;
} else {
if constexpr (tools::is_unsigned_v<std::common_type_t<M, N>>) {
return 0;
} else {
return x / y;
}
}
} else {
if (x >= 0) {
if constexpr (tools::is_unsigned_v<std::common_type_t<M, N>>) {
return 0;
} else {
return x / y;
}
} else {
return (x + 1) / y + 1;
}
}
}
}
#line 7 "tools/block_ceil.hpp"
namespace tools {
template <typename M, typename N>
constexpr std::common_type_t<M, N> block_ceil(const M x, const N y) noexcept {
assert(y > 0);
return tools::ceil(x, y) * y;
}
}
#line 1 "tools/chmin.hpp"
#line 1 "tools/cmp_less.hpp"
#line 1 "tools/is_signed.hpp"
#line 5 "tools/is_signed.hpp"
namespace tools {
template <typename T>
struct is_signed : std::is_signed<T> {};
template <typename T>
inline constexpr bool is_signed_v = tools::is_signed<T>::value;
}
#line 1 "tools/make_unsigned.hpp"
#line 5 "tools/make_unsigned.hpp"
namespace tools {
template <typename T>
struct make_unsigned : std::make_unsigned<T> {};
template <typename T>
using make_unsigned_t = typename tools::make_unsigned<T>::type;
}
#line 7 "tools/cmp_less.hpp"
namespace tools {
template <tools::integral T, tools::integral U>
constexpr bool cmp_less(const T t, const U u) noexcept {
using UT = tools::make_unsigned_t<T>;
using UU = tools::make_unsigned_t<U>;
if constexpr (tools::is_signed_v<T> == tools::is_signed_v<U>) {
return t < u;
} else if constexpr (tools::is_signed_v<T>) {
return t < 0 ? true : static_cast<UT>(t) < u;
} else {
return u < 0 ? false : t < static_cast<UU>(u);
}
}
}
#line 6 "tools/chmin.hpp"
namespace tools {
template <typename M, typename N>
bool chmin(M& lhs, const N& rhs) {
bool updated;
if constexpr (tools::integral<M> && tools::integral<N>) {
updated = tools::cmp_less(rhs, lhs);
} else {
updated = rhs < lhs;
}
if (updated) lhs = rhs;
return updated;
}
}
#line 1 "tools/extgcd.hpp"
#line 1 "tools/signed_integral.hpp"
#line 6 "tools/signed_integral.hpp"
namespace tools {
template <typename T>
concept signed_integral = tools::integral<T> && tools::is_signed_v<T>;
}
#line 12 "tools/extgcd.hpp"
namespace tools {
namespace detail::extgcd {
template <typename M, typename N>
struct impl {
using T = std::common_type_t<M, N>;
constexpr std::tuple<T, T, T> operator()(const M a, const N b) const noexcept requires (tools::signed_integral<M> && tools::signed_integral<N>) {
T prev_r = static_cast<T>(a);
T r = static_cast<T>(b);
const bool prev_r_is_neg = prev_r < T(0);
const bool r_is_neg = r < T(0);
if (prev_r_is_neg) prev_r = -prev_r;
if (r_is_neg) r = -r;
T prev_s(1);
T prev_t(0);
T s(0);
T t(1);
while (r != T(0)) {
const T q = prev_r / r;
std::tie(prev_r, r) = std::make_pair(r, prev_r - q * r);
std::tie(prev_s, s) = std::make_pair(s, prev_s - q * s);
std::tie(prev_t, t) = std::make_pair(t, prev_t - q * t);
}
if (prev_r_is_neg) prev_s = -prev_s;
if (r_is_neg) prev_t = -prev_t;
assert(tools::abs(prev_s) <= std::max(tools::abs(T(b)) / prev_r / T(2), T(1)));
assert(tools::abs(prev_t) <= std::max(tools::abs(T(a)) / prev_r / T(2), T(1)));
return std::make_tuple(prev_s, prev_t, prev_r);
}
};
}
template <typename M, typename N>
constexpr decltype(auto) extgcd(M&& m, N&& n) noexcept(noexcept(tools::detail::extgcd::impl<std::remove_cvref_t<M>, std::remove_cvref_t<N>>{}(std::forward<M>(m), std::forward<N>(n)))) {
return tools::detail::extgcd::impl<std::remove_cvref_t<M>, std::remove_cvref_t<N>>{}(std::forward<M>(m), std::forward<N>(n));
}
}
#line 1 "tools/floor.hpp"
#line 7 "tools/floor.hpp"
namespace tools {
template <tools::non_bool_integral M, tools::non_bool_integral N>
constexpr std::common_type_t<M, N> floor(const M x, const N y) noexcept {
assert(y != 0);
if (y >= 0) {
if (x >= 0) {
return x / y;
} else {
return (x + 1) / y - 1;
}
} else {
if (x > 0) {
return (x - 1) / y - 1;
} else {
return x / y;
}
}
}
}
#line 1 "tools/floor_log2.hpp"
#line 1 "tools/bit_width.hpp"
#include <bit>
#line 12 "tools/bit_width.hpp"
namespace tools {
namespace detail::bit_width {
template <tools::non_bool_integral T>
struct impl {
constexpr int operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
assert(x >= 0);
return impl<tools::make_unsigned_t<T>>{}(x);
}
constexpr int operator()(const T x) const noexcept(noexcept(std::bit_width(x))) requires tools::is_unsigned_v<T> {
return std::bit_width(x);
}
};
}
template <typename T>
constexpr decltype(auto) bit_width(T&& x) noexcept(noexcept(tools::detail::bit_width::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::bit_width::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 6 "tools/floor_log2.hpp"
namespace tools {
template <typename T>
constexpr T floor_log2(T x) noexcept {
assert(x > 0);
return tools::bit_width(x) - 1;
}
}
#line 1 "tools/garner2.hpp"
#line 1 "tools/is_prime.hpp"
#line 1 "tools/prod_mod.hpp"
#line 1 "tools/uint128_t.hpp"
#line 1 "tools/detail/int128_t_and_uint128_t.hpp"
#line 8 "tools/detail/int128_t_and_uint128_t.hpp"
#include <functional>
#line 1 "tools/bit_ceil.hpp"
#line 12 "tools/bit_ceil.hpp"
namespace tools {
namespace detail::bit_ceil {
template <tools::non_bool_integral T>
struct impl {
constexpr T operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
assert(x >= 0);
return impl<tools::make_unsigned_t<T>>{}(x);
}
constexpr T operator()(const T x) const noexcept(noexcept(std::bit_ceil(x))) requires tools::is_unsigned_v<T> {
return std::bit_ceil(x);
}
};
}
template <typename T>
constexpr decltype(auto) bit_ceil(T&& x) noexcept(noexcept(tools::detail::bit_ceil::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::bit_ceil::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 1 "tools/bit_floor.hpp"
#line 12 "tools/bit_floor.hpp"
namespace tools {
namespace detail::bit_floor {
template <tools::non_bool_integral T>
struct impl {
constexpr T operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
assert(x >= 0);
return impl<tools::make_unsigned_t<T>>{}(x);
}
constexpr T operator()(const T x) const noexcept(noexcept(std::bit_floor(x))) requires tools::is_unsigned_v<T> {
return std::bit_floor(x);
}
};
}
template <typename T>
constexpr decltype(auto) bit_floor(T&& x) noexcept(noexcept(tools::detail::bit_floor::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::bit_floor::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 1 "tools/countr_zero.hpp"
#line 14 "tools/countr_zero.hpp"
namespace tools {
namespace detail::countr_zero {
template <tools::non_bool_integral T>
struct impl {
constexpr int operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
assert(x >= 0);
return std::min(impl<tools::make_unsigned_t<T>>{}(x), std::numeric_limits<T>::digits);
}
constexpr int operator()(const T x) const noexcept(noexcept(std::countr_zero(x))) requires tools::is_unsigned_v<T> {
return std::countr_zero(x);
}
};
}
template <typename T>
constexpr decltype(auto) countr_zero(T&& x) noexcept(noexcept(tools::detail::countr_zero::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::countr_zero::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 1 "tools/gcd.hpp"
#line 7 "tools/gcd.hpp"
namespace tools {
namespace detail::gcd {
template <typename M, typename N>
struct impl {
constexpr decltype(auto) operator()(const M m, const N n) const noexcept(noexcept(std::gcd(m, n))) {
return std::gcd(m, n);
}
};
}
template <typename M, typename N>
constexpr decltype(auto) gcd(M&& m, N&& n) noexcept(noexcept(tools::detail::gcd::impl<std::remove_cvref_t<M>, std::remove_cvref_t<N>>{}(std::forward<M>(m), std::forward<N>(n)))) {
return tools::detail::gcd::impl<std::remove_cvref_t<M>, std::remove_cvref_t<N>>{}(std::forward<M>(m), std::forward<N>(n));
}
}
#line 1 "tools/has_single_bit.hpp"
#line 12 "tools/has_single_bit.hpp"
namespace tools {
namespace detail::has_single_bit {
template <tools::non_bool_integral T>
struct impl {
constexpr bool operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
assert(x >= 0);
return impl<tools::make_unsigned_t<T>>{}(x);
}
constexpr bool operator()(const T x) const noexcept(noexcept(std::has_single_bit(x))) requires tools::is_unsigned_v<T> {
return std::has_single_bit(x);
}
};
}
template <typename T>
constexpr decltype(auto) has_single_bit(T&& x) noexcept(noexcept(tools::detail::has_single_bit::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::has_single_bit::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 1 "tools/hash_combine.hpp"
#line 6 "tools/hash_combine.hpp"
// Source: https://github.com/google/cityhash/blob/f5dc54147fcce12cefd16548c8e760d68ac04226/src/city.h
// License: MIT
// Author: Google Inc.
// Copyright (c) 2011 Google, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
namespace tools {
template <typename T>
void hash_combine(std::size_t& seed, const T& v) {
static const std::hash<T> hasher;
static constexpr std::size_t k_mul = 0x9ddfea08eb382d69ULL;
std::size_t a = (hasher(v) ^ seed) * k_mul;
a ^= (a >> 47);
std::size_t b = (seed ^ a) * k_mul;
b ^= (b >> 47);
seed = b * k_mul;
}
}
#line 1 "tools/make_signed.hpp"
#line 5 "tools/make_signed.hpp"
namespace tools {
template <typename T>
struct make_signed : std::make_signed<T> {};
template <typename T>
using make_signed_t = typename tools::make_signed<T>::type;
}
#line 1 "tools/now.hpp"
#include <chrono>
namespace tools {
inline long long now() {
return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}
}
#line 1 "tools/popcount.hpp"
#line 12 "tools/popcount.hpp"
namespace tools {
namespace detail::popcount {
template <tools::non_bool_integral T>
struct impl {
constexpr int operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
assert(x >= 0);
return impl<tools::make_unsigned_t<T>>{}(x);
}
constexpr int operator()(const T x) const noexcept(noexcept(std::popcount(x))) requires tools::is_unsigned_v<T> {
return std::popcount(x);
}
};
}
template <typename T>
constexpr decltype(auto) popcount(T&& x) noexcept(noexcept(tools::detail::popcount::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::popcount::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 31 "tools/detail/int128_t_and_uint128_t.hpp"
namespace tools {
using uint128_t = unsigned __int128;
using int128_t = __int128;
template <>
struct is_integral<tools::int128_t> : std::true_type {};
template <>
struct is_integral<tools::uint128_t> : std::true_type {};
template <>
struct is_integral<const tools::int128_t> : std::true_type {};
template <>
struct is_integral<const tools::uint128_t> : std::true_type {};
template <>
struct is_integral<volatile tools::int128_t> : std::true_type {};
template <>
struct is_integral<volatile tools::uint128_t> : std::true_type {};
template <>
struct is_integral<const volatile tools::int128_t> : std::true_type {};
template <>
struct is_integral<const volatile tools::uint128_t> : std::true_type {};
template <>
struct is_signed<tools::int128_t> : std::true_type {};
template <>
struct is_signed<tools::uint128_t> : std::false_type {};
template <>
struct is_signed<const tools::int128_t> : std::true_type {};
template <>
struct is_signed<const tools::uint128_t> : std::false_type {};
template <>
struct is_signed<volatile tools::int128_t> : std::true_type {};
template <>
struct is_signed<volatile tools::uint128_t> : std::false_type {};
template <>
struct is_signed<const volatile tools::int128_t> : std::true_type {};
template <>
struct is_signed<const volatile tools::uint128_t> : std::false_type {};
template <>
struct is_unsigned<tools::int128_t> : std::false_type {};
template <>
struct is_unsigned<tools::uint128_t> : std::true_type {};
template <>
struct is_unsigned<const tools::int128_t> : std::false_type {};
template <>
struct is_unsigned<const tools::uint128_t> : std::true_type {};
template <>
struct is_unsigned<volatile tools::int128_t> : std::false_type {};
template <>
struct is_unsigned<volatile tools::uint128_t> : std::true_type {};
template <>
struct is_unsigned<const volatile tools::int128_t> : std::false_type {};
template <>
struct is_unsigned<const volatile tools::uint128_t> : std::true_type {};
template <>
struct make_signed<tools::int128_t> {
using type = tools::int128_t;
};
template <>
struct make_signed<tools::uint128_t> {
using type = tools::int128_t;
};
template <>
struct make_signed<const tools::int128_t> {
using type = const tools::int128_t;
};
template <>
struct make_signed<const tools::uint128_t> {
using type = const tools::int128_t;
};
template <>
struct make_signed<volatile tools::int128_t> {
using type = volatile tools::int128_t;
};
template <>
struct make_signed<volatile tools::uint128_t> {
using type = volatile tools::int128_t;
};
template <>
struct make_signed<const volatile tools::int128_t> {
using type = const volatile tools::int128_t;
};
template <>
struct make_signed<const volatile tools::uint128_t> {
using type = const volatile tools::int128_t;
};
template <>
struct make_unsigned<tools::int128_t> {
using type = tools::uint128_t;
};
template <>
struct make_unsigned<tools::uint128_t> {
using type = tools::uint128_t;
};
template <>
struct make_unsigned<const tools::int128_t> {
using type = const tools::uint128_t;
};
template <>
struct make_unsigned<const tools::uint128_t> {
using type = const tools::uint128_t;
};
template <>
struct make_unsigned<volatile tools::int128_t> {
using type = volatile tools::uint128_t;
};
template <>
struct make_unsigned<volatile tools::uint128_t> {
using type = volatile tools::uint128_t;
};
template <>
struct make_unsigned<const volatile tools::int128_t> {
using type = const volatile tools::uint128_t;
};
template <>
struct make_unsigned<const volatile tools::uint128_t> {
using type = const volatile tools::uint128_t;
};
namespace detail::int128_t {
constexpr tools::uint128_t parse_unsigned(const std::string_view s) noexcept {
assert(!s.empty());
tools::uint128_t x = 0;
std::size_t i = s[0] == '+';
if (i + 1 < s.size() && s[i] == '0' && (s[i + 1] == 'x' || s[i + 1] == 'X')) {
for (i += 2; i < s.size(); ++i) {
assert(('0' <= s[i] && s[i] <= '9') || ('a' <= s[i] && s[i] <= 'f') || ('A' <= s[i] && s[i] <= 'F'));
x <<= 4;
if ('0' <= s[i] && s[i] <= '9') {
x |= s[i] - '0';
} else if ('a' <= s[i] && s[i] <= 'f') {
x |= s[i] - 'a' + 10;
} else {
x |= s[i] - 'A' + 10;
}
}
} else {
for (; i < s.size(); ++i) {
assert('0' <= s[i] && s[i] <= '9');
x *= 10;
x += s[i] - '0';
}
}
return x;
}
constexpr tools::int128_t parse_signed(const std::string_view s) noexcept {
assert(!s.empty());
tools::int128_t x = 0;
if (s[0] == '-') {
std::size_t i = 1;
if (i + 1 < s.size() && s[i] == '0' && (s[i + 1] == 'x' || s[i + 1] == 'X')) {
for (i += 2; i < s.size(); ++i) {
assert(('0' <= s[i] && s[i] <= '9') || ('a' <= s[i] && s[i] <= 'f') || ('A' <= s[i] && s[i] <= 'F'));
x *= 16;
if ('0' <= s[i] && s[i] <= '9') {
x -= s[i] - '0';
} else if ('a' <= s[i] && s[i] <= 'f') {
x -= s[i] - 'a' + 10;
} else {
x -= s[i] - 'A' + 10;
}
}
} else {
for (; i < s.size(); ++i) {
assert('0' <= s[i] && s[i] <= '9');
x *= 10;
x -= s[i] - '0';
}
}
} else {
std::size_t i = s[0] == '+';
if (i + 1 < s.size() && s[i] == '0' && (s[i + 1] == 'x' || s[i + 1] == 'X')) {
for (i += 2; i < s.size(); ++i) {
assert(('0' <= s[i] && s[i] <= '9') || ('a' <= s[i] && s[i] <= 'f') || ('A' <= s[i] && s[i] <= 'F'));
x <<= 4;
if ('0' <= s[i] && s[i] <= '9') {
x |= s[i] - '0';
} else if ('a' <= s[i] && s[i] <= 'f') {
x |= s[i] - 'a' + 10;
} else {
x |= s[i] - 'A' + 10;
}
}
} else {
for (; i < s.size(); ++i) {
assert('0' <= s[i] && s[i] <= '9');
x *= 10;
x += s[i] - '0';
}
}
}
return x;
}
}
}
#define UINT128_C(c) tools::detail::int128_t::parse_unsigned(#c)
#define INT128_C(c) tools::detail::int128_t::parse_signed(#c)
inline std::istream& operator>>(std::istream& is, tools::uint128_t& x) {
std::string s;
is >> s;
x = tools::detail::int128_t::parse_unsigned(s);
return is;
}
inline std::istream& operator>>(std::istream& is, tools::int128_t& x) {
std::string s;
is >> s;
x = tools::detail::int128_t::parse_signed(s);
return is;
}
inline std::ostream& operator<<(std::ostream& os, tools::uint128_t x) {
std::string s;
if (x > 0) {
while (x > 0) {
s.push_back('0' + x % 10);
x /= 10;
}
} else {
s.push_back('0');
}
std::ranges::reverse(s);
return os << s;
}
inline std::ostream& operator<<(std::ostream& os, tools::int128_t x) {
std::string s;
if (x > 0) {
while (x > 0) {
s.push_back('0' + x % 10);
x /= 10;
}
} else if (x < 0) {
while (x < 0) {
s.push_back('0' + (-(x % 10)));
x /= 10;
}
s.push_back('-');
} else {
s.push_back('0');
}
std::ranges::reverse(s);
return os << s;
}
#if defined(__GLIBCXX__) && defined(__STRICT_ANSI__)
namespace std {
template <>
struct hash<tools::uint128_t> {
std::size_t operator()(const tools::uint128_t& x) const {
static const std::size_t seed = tools::now();
std::size_t hash = seed;
tools::hash_combine(hash, static_cast<std::uint64_t>(x >> 64));
tools::hash_combine(hash, static_cast<std::uint64_t>(x & ((UINT128_C(1) << 64) - 1)));
return hash;
}
};
template <>
struct hash<tools::int128_t> {
std::size_t operator()(const tools::int128_t& x) const {
static std::hash<tools::uint128_t> hasher;
return hasher(static_cast<tools::uint128_t>(x));
}
};
}
#endif
namespace tools {
template <>
struct detail::abs::impl<tools::int128_t> {
constexpr tools::int128_t operator()(const tools::int128_t& x) const noexcept {
return x >= 0 ? x : -x;
}
};
#if defined(__GLIBCXX__) && defined(__STRICT_ANSI__)
template <>
struct detail::bit_ceil::impl<tools::uint128_t> {
constexpr tools::uint128_t operator()(tools::uint128_t x) const noexcept {
if (x <= 1) return 1;
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
x |= x >> 64;
return ++x;
}
};
template <>
struct detail::bit_floor::impl<tools::uint128_t> {
constexpr tools::uint128_t operator()(tools::uint128_t x) const noexcept {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
x |= x >> 64;
return x & ~(x >> 1);
}
};
template <>
struct detail::bit_width::impl<tools::uint128_t> {
constexpr int operator()(tools::uint128_t x) const noexcept {
int w = 0;
if (x & UINT128_C(0xffffffffffffffff0000000000000000)) {
x >>= 64;
w += 64;
}
if (x & UINT128_C(0xffffffff00000000)) {
x >>= 32;
w += 32;
}
if (x & UINT128_C(0xffff0000)) {
x >>= 16;
w += 16;
}
if (x & UINT128_C(0xff00)) {
x >>= 8;
w += 8;
}
if (x & UINT128_C(0xf0)) {
x >>= 4;
w += 4;
}
if (x & UINT128_C(0xc)) {
x >>= 2;
w += 2;
}
if (x & UINT128_C(0x2)) {
x >>= 1;
w += 1;
}
w += x;
return w;
}
};
template <>
class detail::countr_zero::impl<tools::uint128_t> {
using type = tools::uint128_t;
static constexpr int shift = 120;
static constexpr type magic = UINT128_C(0x01061438916347932a5cd9d3ead7b77f);
static constexpr int ntz_table[255] = {
128, 0, 1, -1, 2, -1, 8, -1, 3, -1, 15, -1, 9, -1, 22, -1,
4, -1, 29, -1, 16, -1, 36, -1, 10, -1, 43, -1, 23, -1, 50, -1,
5, -1, 33, -1, 30, -1, 57, -1, 17, -1, 64, -1, 37, -1, 71, -1,
11, -1, 60, -1, 44, -1, 78, -1, 24, -1, 85, -1, 51, -1, 92, -1,
-1, 6, -1, 20, -1, 34, -1, 48, 31, -1, -1, 69, 58, -1, -1, 90,
18, -1, 67, -1, 65, -1, 99, -1, 38, -1, 101, -1, 72, -1, 106, -1,
-1, 12, -1, 40, -1, 61, -1, 82, 45, -1, -1, 103, 79, -1, 113, -1,
-1, 25, -1, 74, 86, -1, -1, 116, -1, 52, -1, 108, -1, 93, -1, 120,
127, -1, -1, 7, -1, 14, -1, 21, -1, 28, -1, 35, -1, 42, -1, 49,
-1, 32, -1, 56, -1, 63, -1, 70, -1, 59, -1, 77, -1, 84, -1, 91,
-1, 19, -1, 47, -1, 68, -1, 89, -1, 66, -1, 98, -1, 100, -1, 105,
-1, 39, -1, 81, -1, 102, -1, 112, -1, 73, -1, 115, -1, 107, -1, 119,
126, -1, 13, -1, 27, -1, 41, -1, -1, 55, 62, -1, -1, 76, 83, -1,
-1, 46, -1, 88, -1, 97, -1, 104, -1, 80, -1, 111, -1, 114, -1, 118,
125, -1, 26, -1, 54, -1, 75, -1, -1, 87, 96, -1, -1, 110, -1, 117,
124, -1, 53, -1, -1, 95, 109, -1, 123, -1, 94, -1, 122, -1, 121
};
public:
constexpr int operator()(const type& x) const noexcept {
return ntz_table[static_cast<type>(magic * static_cast<type>(x & -x)) >> shift];
}
};
namespace detail::gcd {
template <>
struct impl<tools::uint128_t, tools::uint128_t> {
constexpr tools::uint128_t operator()(tools::uint128_t m, tools::uint128_t n) const noexcept {
while (n != 0) {
m %= n;
std::swap(m, n);
}
return m;
};
};
template <typename T>
concept non_bool_integral_at_most_128bit = tools::non_bool_integral<T> && std::numeric_limits<T>::digits <= 128;
template <typename T>
concept non_bool_integral_at_most_64bit = tools::non_bool_integral<T> && std::numeric_limits<T>::digits <= 64;
template <typename M, typename N> requires (
(non_bool_integral_at_most_128bit<M> && non_bool_integral_at_most_128bit<N>)
&& !(non_bool_integral_at_most_64bit<M> && non_bool_integral_at_most_64bit<N>)
&& !(std::same_as<M, tools::uint128_t> && std::same_as<N, tools::uint128_t>)
)
struct impl<M, N> {
constexpr std::common_type_t<M, N> operator()(const M m, const N n) const noexcept {
return std::common_type_t<M, N>(
tools::gcd(
m >= 0 ? tools::uint128_t(m) : tools::uint128_t(-(m + 1)) + 1,
n >= 0 ? tools::uint128_t(n) : tools::uint128_t(-(n + 1)) + 1
)
);
}
};
}
template <>
struct detail::has_single_bit::impl<tools::uint128_t> {
constexpr bool operator()(tools::uint128_t x) const noexcept {
return x != 0 && (x & (x - 1)) == 0;
}
};
template <>
struct detail::popcount::impl<tools::uint128_t> {
constexpr int operator()(tools::uint128_t x) const noexcept {
x = (x & UINT128_C(0x55555555555555555555555555555555)) + (x >> 1 & UINT128_C(0x55555555555555555555555555555555));
x = (x & UINT128_C(0x33333333333333333333333333333333)) + (x >> 2 & UINT128_C(0x33333333333333333333333333333333));
x = (x & UINT128_C(0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)) + (x >> 4 & UINT128_C(0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f));
x = (x & UINT128_C(0x00ff00ff00ff00ff00ff00ff00ff00ff)) + (x >> 8 & UINT128_C(0x00ff00ff00ff00ff00ff00ff00ff00ff));
x = (x & UINT128_C(0x0000ffff0000ffff0000ffff0000ffff)) + (x >> 16 & UINT128_C(0x0000ffff0000ffff0000ffff0000ffff));
x = (x & UINT128_C(0x00000000ffffffff00000000ffffffff)) + (x >> 32 & UINT128_C(0x00000000ffffffff00000000ffffffff));
x = (x & UINT128_C(0x0000000000000000ffffffffffffffff)) + (x >> 64 & UINT128_C(0x0000000000000000ffffffffffffffff));
return x;
}
};
#endif
}
#line 5 "tools/uint128_t.hpp"
#line 5 "tools/prod_mod.hpp"
namespace tools {
template <typename T1, typename T2, typename T3>
constexpr T3 prod_mod(const T1 x, const T2 y, const T3 m) {
using u128 = tools::uint128_t;
u128 prod_mod = u128(x >= 0 ? x : -x) * u128(y >= 0 ? y : -y) % u128(m);
if ((x >= 0) ^ (y >= 0)) prod_mod = u128(m) - prod_mod;
return prod_mod;
}
}
#line 1 "tools/pow_mod.hpp"
#line 1 "tools/mod.hpp"
#line 7 "tools/mod.hpp"
namespace tools {
template <tools::non_bool_integral M, tools::non_bool_integral N>
constexpr std::common_type_t<M, N> mod(const M a, const N b) noexcept {
assert(b != 0);
using UM = tools::make_unsigned_t<M>;
using UN = tools::make_unsigned_t<N>;
const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
auto r = ua % ub;
if (a < 0 && r > 0) {
r = ub - r;
}
return r;
}
}
#line 6 "tools/pow_mod.hpp"
namespace tools {
template <typename T1, typename T2, typename T3>
constexpr T3 pow_mod(const T1 x, T2 n, const T3 m) {
if (m == 1) return 0;
T3 r = 1;
T3 y = tools::mod(x, m);
while (n > 0) {
if ((n & 1) > 0) {
r = tools::prod_mod(r, y, m);
}
y = tools::prod_mod(y, y, m);
n /= 2;
}
return r;
}
}
#line 7 "tools/is_prime.hpp"
namespace tools {
constexpr bool is_prime(const unsigned long long n) {
constexpr std::array<unsigned long long, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
auto d = n - 1;
for (; d % 2 == 0; d /= 2);
for (const auto a : bases) {
if (a % n == 0) return true;
auto power = d;
auto target = tools::pow_mod(a, power, n);
bool is_composite = true;
if (target == 1) is_composite = false;
for (; is_composite && power != n - 1; power *= 2, target = tools::prod_mod(target, target, n)) {
if (target == n - 1) is_composite = false;
}
if (is_composite) {
return false;
}
}
return true;
}
}
#line 6 "tools/garner2.hpp"
namespace tools {
template <typename M1, typename M2>
long long garner2(const M1& a, const M2& b) {
using ull = unsigned long long;
static constexpr ull m1_m2 = ull(M1::mod()) * ull(M2::mod());
static const M2 m1_inv_mod_m2 = M2::raw(M1::mod()).inv();
assert(M1::mod() < M2::mod());
assert(tools::is_prime(M1::mod()));
assert(tools::is_prime(M2::mod()));
// t = (b - a) / M1; (mod M2)
// return a + t * M1;
const M2 t = (b - M2::raw(a.val())) * m1_inv_mod_m2;
ull r = t.val();
r *= M1::mod();
r += a.val();
if (r >= m1_m2) r -= m1_m2;
return r;
}
}
#line 1 "tools/int128_t.hpp"
#line 5 "tools/int128_t.hpp"
#line 1 "tools/mutable_type.hpp"
#line 5 "tools/mutable_type.hpp"
namespace tools {
template <typename T>
concept mutable_type = !std::is_const_v<std::remove_reference_t<T>>;
}
#line 1 "tools/pow2.hpp"
#line 7 "tools/pow2.hpp"
namespace tools {
template <tools::integral T>
constexpr T pow2(const T x) noexcept {
assert(0 <= x && x < std::numeric_limits<T>::digits);
return T(1) << x;
}
}
#line 1 "tools/quo.hpp"
#line 6 "tools/quo.hpp"
namespace tools {
template <tools::non_bool_integral M, tools::non_bool_integral N>
constexpr std::common_type_t<M, N> quo(const M a, const N b) noexcept {
assert(b != 0);
if (a >= 0) {
return a / b;
} else {
if (b >= 0) {
return (a + 1) / b - 1;
} else {
return (a + 1) / b + 1;
}
}
}
}
#line 1 "tools/signum.hpp"
#line 9 "tools/signum.hpp"
namespace tools {
namespace detail::signum {
template <typename T>
struct impl {
constexpr int operator()(const T x) const noexcept(noexcept(T(0))) {
if constexpr (tools::is_unsigned_v<T>) {
return T(0) < x;
} else {
return (T(0) < x) - (x < T(0));
}
}
};
template <>
struct impl<std::strong_ordering> {
constexpr int operator()(const std::strong_ordering x) const noexcept {
return (0 < x) - (x < 0);
}
};
template <>
struct impl<std::weak_ordering> {
constexpr int operator()(const std::weak_ordering x) const noexcept {
return (0 < x) - (x < 0);
}
};
template <>
struct impl<std::partial_ordering> {
constexpr int operator()(const std::partial_ordering x) const noexcept {
assert(x != std::partial_ordering::unordered);
return (0 < x) - (x < 0);
}
};
}
template <typename T>
constexpr decltype(auto) signum(T&& x) noexcept(noexcept(tools::detail::signum::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
return tools::detail::signum::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
}
}
#line 1 "tools/unsigned_integral.hpp"
#line 6 "tools/unsigned_integral.hpp"
namespace tools {
template <typename T>
concept unsigned_integral = tools::integral<T> && tools::is_unsigned_v<T>;
}
#line 42 "tools/bigint.hpp"
namespace tools {
class bigint;
template <>
struct detail::abs::impl<tools::bigint> {
tools::bigint operator()(auto&&) const;
};
template <>
struct detail::extgcd::impl<tools::bigint, tools::bigint> {
std::tuple<tools::bigint, tools::bigint, tools::bigint> operator()(tools::bigint, tools::bigint) const;
};
template <>
struct detail::gcd::impl<tools::bigint, tools::bigint> {
struct mat22;
static mat22 half_gcd(tools::bigint& a, tools::bigint& b);
tools::bigint operator()(tools::bigint, tools::bigint) const;
};
template <>
struct detail::signum::impl<tools::bigint> {
int operator()(const tools::bigint&) const;
};
class bigint {
using mint1 = atcoder::static_modint<167772161>;
using mint2 = atcoder::static_modint<469762049>;
bool m_nonnegative;
std::vector<std::int_fast32_t> m_digits;
static constexpr std::int_fast32_t BASE = 10000;
static constexpr std::int_fast32_t LOG10_BASE = 4;
static constexpr std::array<std::int_fast32_t, 5> POW10 = {1, 10, 100, 1000, 10000};
static std::strong_ordering compare_3way_abs(const tools::bigint& lhs, const tools::bigint& rhs) {
if (const auto comp = lhs.m_digits.size() <=> rhs.m_digits.size(); comp != 0) {
return comp;
}
for (std::size_t i = lhs.m_digits.size(); i --> 0;) {
if (const auto comp = lhs.m_digits[i] <=> rhs.m_digits[i]; comp != 0) {
return comp;
}
}
return std::strong_ordering::equal;
}
template <bool PLUS>
auto internal_add(this tools::mutable_type auto&& self, const tools::bigint& other) -> decltype(self) {
if (std::addressof(self) == std::addressof(other)) {
if constexpr (PLUS) {
for (auto& d : self.m_digits) d <<= 1;
self.template regularize<1>();
} else {
self.m_digits.clear();
self.m_nonnegative = true;
}
} else {
const bool this_nonnegative = self.m_nonnegative;
if (!this_nonnegative) {
self.negate();
}
self.m_digits.resize(std::max(self.m_digits.size(), other.m_digits.size()));
if (this_nonnegative == (other.m_nonnegative == PLUS)) {
for (std::size_t i = 0; i < other.m_digits.size(); ++i) {
self.m_digits[i] += other.m_digits[i];
}
} else {
for (std::size_t i = 0; i < other.m_digits.size(); ++i) {
self.m_digits[i] -= other.m_digits[i];
}
}
self.template regularize<1>();
if (!this_nonnegative) {
self.negate();
}
}
return std::forward<decltype(self)>(self);
}
template <int LEVEL> requires (0 <= LEVEL && LEVEL <= 2)
auto regularize(this tools::mutable_type auto&& self) -> decltype(self) {
if constexpr (LEVEL > 0) {
if constexpr (LEVEL == 2) {
for (std::size_t i = 0; i + 1 < self.m_digits.size(); ++i) {
self.m_digits[i + 1] += tools::quo(self.m_digits[i], BASE);
self.m_digits[i] = tools::mod(self.m_digits[i], BASE);
}
} else {
for (std::size_t i = 0; i + 1 < self.m_digits.size(); ++i) {
if (self.m_digits[i] < 0) {
self.m_digits[i] += BASE;
--self.m_digits[i + 1];
} else if (self.m_digits[i] >= BASE) {
self.m_digits[i] -= BASE;
++self.m_digits[i + 1];
}
}
}
if (!self.m_digits.empty() && self.m_digits.back() < 0) {
self.m_nonnegative = !self.m_nonnegative;
for (std::size_t i = 0; i < self.m_digits.size(); ++i) {
self.m_digits[i] = -self.m_digits[i];
}
for (std::size_t i = 0; i + 1 < self.m_digits.size(); ++i) {
if (self.m_digits[i] < 0) {
self.m_digits[i] = BASE + self.m_digits[i];
--self.m_digits[i + 1];
}
}
}
if constexpr (LEVEL == 2) {
while (!self.m_digits.empty() && self.m_digits.back() >= BASE) {
self.m_digits.push_back(self.m_digits.back() / BASE);
self.m_digits[self.m_digits.size() - 2] %= BASE;
}
} else {
if (!self.m_digits.empty() && self.m_digits.back() >= BASE) {
self.m_digits.back() -= BASE;
self.m_digits.push_back(1);
}
}
}
while (!self.m_digits.empty() && self.m_digits.back() == 0) {
self.m_digits.pop_back();
}
if (self.m_digits.empty() && !self.m_nonnegative) {
self.m_nonnegative = true;
}
return std::forward<decltype(self)>(self);
}
public:
bigint() : m_nonnegative(true) {
}
explicit bigint(tools::integral auto n) : m_nonnegative(n >= 0) {
while (n != 0) {
this->m_digits.push_back(n % BASE);
n /= BASE;
}
if (!this->m_nonnegative) {
for (auto& d : this->m_digits) {
d = -d;
}
}
}
explicit bigint(const std::string_view s) {
assert(!s.empty());
std::size_t offset;
if (s[0] == '+') {
this->m_nonnegative = true;
offset = 1;
} else if (s[0] == '-') {
this->m_nonnegative = false;
offset = 1;
} else {
this->m_nonnegative = true;
offset = 0;
}
this->m_digits.reserve(tools::ceil<std::size_t>(s.size() - offset, LOG10_BASE));
for (std::size_t i = 0; i < s.size() - offset; i += LOG10_BASE) {
this->m_digits.push_back(0);
for (std::size_t j = std::min(i + LOG10_BASE, s.size() - offset); j --> i;) {
assert('0' <= s[s.size() - 1 - j] && s[s.size() - 1 - j] <= '9');
this->m_digits.back() = this->m_digits.back() * 10 + (s[s.size() - 1 - j] - '0');
}
}
this->regularize<0>();
}
auto abs_inplace(this tools::mutable_type auto&& self) -> decltype(self) {
if (!self.m_nonnegative) self.negate();
return std::forward<decltype(self)>(self);
}
tools::bigint divide_by_pow10(this auto&& self, const std::ptrdiff_t exponent) {
return tools::bigint(std::forward<decltype(self)>(self)).divide_inplace_by_pow10(exponent);
}
auto divide_inplace_by_pow10(this tools::mutable_type auto&& self, const std::ptrdiff_t exponent) -> decltype(self) {
self.multiply_inplace_by_pow10(-exponent);
return std::forward<decltype(self)>(self);
}
private:
template <tools::unsigned_integral T>
static const tools::bigint& divmod_naive_threshold() {
static const tools::bigint threshold((std::numeric_limits<T>::max() - (BASE - 1)) / BASE);
return threshold;
}
template <tools::unsigned_integral T>
std::pair<tools::bigint, tools::bigint> divmod_naive(const tools::bigint& other) const {
assert(!other.m_digits.empty());
assert(tools::bigint::compare_3way_abs(other, divmod_naive_threshold<T>()) <= 0);
T b = 0;
for (std::size_t i = other.m_digits.size(); i --> 0;) {
b *= BASE;
b += other.m_digits[i];
}
tools::bigint Q(*this);
T r = 0;
for (std::size_t i = Q.m_digits.size(); i--> 0;) {
r *= BASE;
r += Q.m_digits[i];
Q.m_digits[i] = r / b;
r %= b;
}
Q.m_nonnegative = (this->m_nonnegative == other.m_nonnegative);
Q.regularize<0>();
tools::bigint R(r);
R.m_nonnegative = (r == 0 || this->m_nonnegative);
return std::make_pair(std::move(Q), std::move(R));
}
static constexpr std::size_t divmod_div_limit() {
return 48;
}
std::pair<tools::bigint, tools::bigint> divmod_knuth_d(const tools::bigint& other) const {
assert(this->m_nonnegative);
assert(other.m_nonnegative);
assert(!other.m_digits.empty());
assert(BASE <= other.m_digits.back() * 2);
if (*this < other) {
return std::make_pair(tools::bigint{}, *this);
}
tools::bigint R(*this);
R.m_digits.push_back(0);
tools::bigint Q;
Q.m_digits.resize(R.m_digits.size() - other.m_digits.size());
for (int i = Q.m_digits.size() - 1; i >= 0; --i) {
Q.m_digits[i] = std::min((R.m_digits.back() * BASE + R.m_digits.rbegin()[1]) / other.m_digits.back(), BASE - 1);
for (int j = 0; j < std::ssize(other.m_digits); ++j) {
R.m_digits[i + j] -= Q.m_digits[i] * other.m_digits[j];
R.m_digits[i + j + 1] += tools::quo(R.m_digits[i + j], BASE);
R.m_digits[i + j] = tools::mod(R.m_digits[i + j], BASE);
}
while (R.m_digits.back() < 0) {
--Q.m_digits[i];
for (int j = 0; j < std::ssize(other.m_digits); ++j) {
R.m_digits[i + j] += other.m_digits[j];
if (R.m_digits[i + j] >= BASE) {
R.m_digits[i + j] -= BASE;
++R.m_digits[i + j + 1];
}
}
}
R.m_digits.pop_back();
}
while (!Q.m_digits.empty() && Q.m_digits.back() == 0) {
Q.m_digits.pop_back();
}
while (!R.m_digits.empty() && R.m_digits.back() == 0) {
R.m_digits.pop_back();
}
return std::make_pair(std::move(Q), std::move(R));
}
// S1の[l1, r1)桁目 * (BASE ** n1) <=> S2の[l2, r2)桁目 * (BASE ** n2)
static std::strong_ordering compare_3way_abs(const tools::bigint& S1, std::size_t l1, std::size_t r1, std::size_t n1, const tools::bigint& S2, std::size_t l2, std::size_t r2, std::size_t n2) {
assert(l1 <= r1);
assert(l2 <= r2);
tools::chmin(l1, S1.m_digits.size());
tools::chmin(r1, S1.m_digits.size());
tools::chmin(l2, S2.m_digits.size());
tools::chmin(r2, S2.m_digits.size());
const auto n_min = std::min(n1, n2);
n1 -= n_min;
n2 -= n_min;
if (const auto comp = (r1 - l1 + n1) <=> (r2 - l2 + n2); comp != 0) {
return comp;
}
if (n1 > 0) {
const auto m2 = r2 - (r1 - l1);
for (std::size_t i1 = r1, i2 = r2; --i1, i2 --> m2;) {
if (const auto comp = S1.m_digits[i1] <=> S2.m_digits[i2]; comp != 0) {
return comp;
}
}
for (std::size_t i2 = m2; i2 --> l2;) {
if (0 < S2.m_digits[i2]) {
return std::strong_ordering::less;
}
}
} else if (n2 > 0) {
const auto m1 = r1 - (r2 - l2);
for (std::size_t i1 = r1, i2 = r2; --i1, i2 --> l2;) {
if (const auto comp = S1.m_digits[i1] <=> S2.m_digits[i2]; comp != 0) {
return comp;
}
}
for (std::size_t i1 = m1; i1 --> l1;) {
if (S1.m_digits[i1] > 0) {
return std::strong_ordering::greater;
}
}
} else {
for (std::size_t i1 = r1, i2 = r2; --i1, i2 --> l2;) {
if (const auto comp = S1.m_digits[i1] <=> S2.m_digits[i2]; comp != 0) {
return comp;
}
}
}
return std::strong_ordering::equal;
}
// *thisの[l, r)桁目
tools::bigint slice(std::size_t l, std::size_t r) const {
assert(this->m_nonnegative);
assert(l <= r);
tools::chmin(l, this->m_digits.size());
tools::chmin(r, this->m_digits.size());
tools::bigint S;
S.m_digits.reserve(r - l);
std::copy(this->m_digits.begin() + l, this->m_digits.begin() + r, std::back_inserter(S.m_digits));
S.regularize<0>();
return S;
}
// *this * (BASE ** n)
tools::bigint lshift(const int n) const {
assert(this->m_nonnegative);
if (n == 0) return *this;
if (this->m_digits.empty()) return *this;
tools::bigint S;
S.m_digits.reserve(n + this->m_digits.size());
S.m_digits.resize(n, 0);
std::ranges::copy(this->m_digits, std::back_inserter(S.m_digits));
return S;
}
// *this / (BASE ** n)
tools::bigint rshift(const std::size_t n) const {
assert(this->m_nonnegative);
if (this->m_digits.size() <= n) return tools::bigint{};
tools::bigint S;
S.m_digits.reserve(this->m_digits.size() - n);
std::copy(this->m_digits.begin() + n, this->m_digits.end(), std::back_inserter(S.m_digits));
return S;
}
// *this * (BASE ** (r - l)) + otherの[l, r)桁目
tools::bigint concat(const tools::bigint& other, std::size_t l, std::size_t r) const {
assert(this->m_nonnegative);
assert(other.m_nonnegative);
assert(l < r);
if (this->m_digits.empty()) return other.slice(l, r);
const auto n = r - l;
tools::chmin(l, other.m_digits.size());
tools::chmin(r, other.m_digits.size());
tools::bigint S;
S.m_digits.reserve(this->m_digits.size() + n);
std::copy(other.m_digits.begin() + l, other.m_digits.begin() + r, std::back_inserter(S.m_digits));
std::fill_n(std::back_inserter(S.m_digits), n - (r - l), 0);
std::copy(this->m_digits.begin(), this->m_digits.end(), std::back_inserter(S.m_digits));
return S;
}
std::pair<tools::bigint, tools::bigint> divmod_3n_2n(const tools::bigint& other, const std::size_t n) const {
assert(this->m_nonnegative);
assert(this->m_digits.size() <= n * 3);
assert(other.m_nonnegative);
assert(other.m_digits.size() == n * 2);
assert(BASE <= other.m_digits.back() * 2);
assert(compare_3way_abs(*this, 0, n * 3, 0, other, 0, n * 2, n) < 0);
tools::bigint Q_hat, S, D;
if (compare_3way_abs(*this, n * 2, n * 3, 0, other, n, n * 2, 0) < 0) {
std::tie(Q_hat, S) = this->slice(n, n * 3).divmod_2n_n(other.slice(n, n * 2), n);
D = other.slice(0, n);
D *= Q_hat;
} else {
Q_hat.m_digits.assign(n, BASE - 1);
S = this->slice(n, n * 3);
S += other.slice(n, n * 2);
S -= other.slice(n, n * 2).lshift(n);
D = other.slice(0, n).lshift(n);
D -= other.slice(0, n);
}
auto R_hat = S.concat(*this, 0, n);
R_hat -= D;
while (!R_hat.m_nonnegative) {
R_hat += other;
--Q_hat;
}
return std::make_pair(std::move(Q_hat), std::move(R_hat));
}
std::pair<tools::bigint, tools::bigint> divmod_4n_2n(const tools::bigint& other, const std::size_t n) const {
assert(this->m_nonnegative);
assert(this->m_digits.size() <= n * 4);
assert(other.m_nonnegative);
assert(other.m_digits.size() == n * 2);
assert(BASE <= other.m_digits.back() * 2);
assert(compare_3way_abs(*this, 0, n * 4, 0, other, 0, n * 2, n * 2) < 0);
const auto [Q1, S] = this->slice(n, n * 4).divmod_3n_2n(other, n);
auto [Q0, R] = S.concat(*this, 0, n).divmod_3n_2n(other, n);
return std::make_pair(Q1.concat(Q0, 0, n), std::move(R));
}
std::pair<tools::bigint, tools::bigint> divmod_2n_n(const tools::bigint& other, const std::size_t n) const {
assert(this->m_nonnegative);
assert(this->m_digits.size() <= n * 2);
assert(other.m_nonnegative);
assert(other.m_digits.size() == n);
assert(BASE <= other.m_digits.back() * 2);
if (other.m_digits.size() <= 3) {
return this->divmod_naive<std::uint_fast64_t>(other);
}
if (other.m_digits.size() <= 8) {
return this->divmod_naive<tools::uint128_t>(other);
}
if (other.m_digits.size() <= tools::bigint::divmod_div_limit()) {
return this->divmod_knuth_d(other);
}
assert(n % 2 == 0);
return this->divmod_4n_2n(other, n / 2);
}
public:
std::pair<tools::bigint, tools::bigint> divmod(const tools::bigint& other) const {
assert(!other.m_digits.empty());
if (tools::bigint::compare_3way_abs(*this, other) < 0) {
return std::make_pair(tools::bigint{}, *this);
}
if (tools::bigint::compare_3way_abs(other, divmod_naive_threshold<std::uint_fast64_t>()) <= 0) {
return this->divmod_naive<std::uint_fast64_t>(other);
}
if (tools::bigint::compare_3way_abs(other, divmod_naive_threshold<tools::uint128_t>()) <= 0) {
return this->divmod_naive<tools::uint128_t>(other);
}
if (!this->m_nonnegative || !other.m_nonnegative) {
auto [Q, R] = tools::abs(*this).divmod(tools::abs(other));
Q.m_nonnegative = Q.m_digits.empty() || (this->m_nonnegative == other.m_nonnegative);
R.m_nonnegative = R.m_digits.empty() || this->m_nonnegative;
return std::make_pair(std::move(Q), std::move(R));
}
if (other.m_digits.size() <= tools::bigint::divmod_div_limit()) {
const auto sigma = BASE / (other.m_digits.back() + 1);
tools::bigint A(*this);
for (auto& A_i : A.m_digits) A_i *= sigma;
A.regularize<2>();
tools::bigint B(other);
for (auto& B_i : B.m_digits) B_i *= sigma;
B.regularize<2>();
auto [Q, R] = A.divmod_knuth_d(B);
return std::make_pair(std::move(Q), R.divmod_naive<std::uint_fast64_t>(tools::bigint(sigma)).first);
}
const auto s = other.m_digits.size();
const auto m = tools::pow2(tools::floor_log2(s / tools::bigint::divmod_div_limit()) + 1);
const auto n = tools::block_ceil(s, m);
const auto sigma1 = n - s;
auto sigma2 = tools::pow2(tools::floor_log2(BASE / (other.m_digits.back() + 1)));
auto B = other.lshift(sigma1);
for (auto& B_i : B.m_digits) B_i *= sigma2;
B.regularize<2>();
assert(B.m_digits.size() == n);
while (B.m_digits.back() * 2 < BASE) {
sigma2 *= 2;
B += B;
assert(B.m_digits.size() == n);
}
auto A = this->lshift(sigma1);
for (auto& A_i : A.m_digits) A_i *= sigma2;
A.regularize<2>();
const auto t = std::max<std::size_t>(2, tools::ceil(A.m_digits.size() + 1, n));
tools::bigint Q, Q_i, R_i;
Q.m_digits.resize(n * (t - 1));
auto Z = A.slice(n * (t - 2), n * t);
std::tie(Q_i, R_i) = Z.divmod_2n_n(B, n);
std::ranges::copy(Q_i.m_digits, Q.m_digits.begin() + n * (t - 2));
for (std::size_t i = t - 2; i --> 0;) {
Z = R_i.concat(A, n * i, n * (i + 1));
std::tie(Q_i, R_i) = Z.divmod_2n_n(B, n);
std::ranges::copy(Q_i.m_digits, Q.m_digits.begin() + n * i);
}
return std::make_pair(std::move(Q.regularize<0>()), R_i.divmod_naive<std::uint_fast64_t>(tools::bigint(sigma2)).first.rshift(sigma1));
}
tools::bigint multiply_by_pow10(this auto&& self, const std::ptrdiff_t exponent) {
return tools::bigint(std::forward<decltype(self)>(self)).multiply_inplace_by_pow10(exponent);
}
auto multiply_inplace_by_pow10(this tools::mutable_type auto&& self, const std::ptrdiff_t exponent) -> decltype(self) {
if (!self.m_digits.empty()) {
const std::ptrdiff_t exponent10000 = tools::floor(exponent, LOG10_BASE);
std::int_fast32_t mod = 0;
if (exponent10000 > 0) {
std::vector<std::int_fast32_t> zero(exponent10000, 0);
self.m_digits.insert(self.m_digits.begin(), zero.begin(), zero.end());
} else if (exponent10000 < 0) {
if (std::ssize(self.m_digits) >= -exponent10000) {
mod = self.m_digits[-exponent10000 - 1] / POW10[LOG10_BASE * (exponent10000 + 1) - exponent];
}
self.m_digits.erase(self.m_digits.begin(), self.m_digits.begin() + std::min<std::size_t>(-exponent10000, self.m_digits.size()));
}
if (const std::int_fast32_t coefficient = POW10[exponent - LOG10_BASE * exponent10000]; coefficient > POW10[0]) {
for (auto& d : self.m_digits) {
d *= coefficient;
}
if (mod > 0) {
if (self.m_digits.empty()) {
self.m_digits.push_back(0);
}
self.m_digits[0] += mod;
}
self.template regularize<2>();
} else {
self.template regularize<0>();
}
}
return std::forward<decltype(self)>(self);
}
auto negate(this tools::mutable_type auto&& self) -> decltype(self) {
if (!self.m_digits.empty()) {
self.m_nonnegative = !self.m_nonnegative;
}
return std::forward<decltype(self)>(self);
}
std::size_t size() const {
if (this->m_digits.empty()) return 0;
return LOG10_BASE * (this->m_digits.size() - 1) + std::distance(POW10.begin(), std::upper_bound(POW10.begin(), POW10.end(), this->m_digits[this->m_digits.size() - 1]));
}
std::int_fast32_t operator[](const std::size_t i) const {
return i < LOG10_BASE * this->m_digits.size() ? this->m_digits[i / LOG10_BASE] / POW10[i % LOG10_BASE] % 10 : 0;
}
friend std::strong_ordering operator<=>(const tools::bigint& lhs, const tools::bigint& rhs) {
if (!lhs.m_nonnegative && rhs.m_nonnegative) return std::strong_ordering::less;
if (lhs.m_nonnegative && !rhs.m_nonnegative) return std::strong_ordering::greater;
const auto comp = tools::bigint::compare_3way_abs(lhs, rhs);
return lhs.m_nonnegative ? comp : 0 <=> comp;
}
friend bool operator==(const tools::bigint& lhs, const tools::bigint& rhs) {
return lhs.m_nonnegative == rhs.m_nonnegative && lhs.m_digits == rhs.m_digits;
}
tools::bigint operator+(this auto&& self) {
return std::forward<decltype(self)>(self);
}
tools::bigint operator-(this auto&& self) {
return tools::bigint(std::forward<decltype(self)>(self)).negate();
}
auto operator++(this tools::mutable_type auto&& self) -> decltype(self) {
self += tools::bigint(1);
return std::forward<decltype(self)>(self);
}
tools::bigint operator++(int) {
tools::bigint old(*this);
++(*this);
return old;
}
auto operator--(this tools::mutable_type auto&& self) -> decltype(self) {
self -= tools::bigint(1);
return std::forward<decltype(self)>(self);
}
tools::bigint operator--(int) {
tools::bigint old(*this);
--(*this);
return old;
}
auto operator+=(this tools::mutable_type auto&& self, const tools::bigint& other) -> decltype(self) {
self.template internal_add<true>(other);
return std::forward<decltype(self)>(self);
}
tools::bigint operator+(this auto&& lhs, const tools::bigint& rhs) {
return tools::bigint(std::forward<decltype(lhs)>(lhs)) += rhs;
}
auto operator-=(this tools::mutable_type auto&& self, const tools::bigint& other) -> decltype(self) {
self.template internal_add<false>(other);
return std::forward<decltype(self)>(self);
}
tools::bigint operator-(this auto&& lhs, const tools::bigint& rhs) {
return tools::bigint(std::forward<decltype(lhs)>(lhs)) -= rhs;
}
auto operator*=(this tools::mutable_type auto&& self, const tools::bigint& other) -> decltype(self) {
// Constraint derived from atcoder::convolution
assert(self.m_digits.size() + other.m_digits.size() <= tools::pow2(25) + 1);
const auto c1 = atcoder::convolution(
self.m_digits | std::views::transform(mint1::raw) | std::ranges::to<std::vector>(),
other.m_digits | std::views::transform(mint1::raw) | std::ranges::to<std::vector>()
);
const auto c2 = atcoder::convolution(
self.m_digits | std::views::transform(mint2::raw) | std::ranges::to<std::vector>(),
other.m_digits | std::views::transform(mint2::raw) | std::ranges::to<std::vector>()
);
self.m_digits.clear();
self.m_digits.reserve(c1.size() + 1);
long long carry = 0;
for (std::size_t i = 0; i < c1.size(); ++i) {
// Since a_i <= 10^4 - 1 and b_i <= 10^4 - 1, c_i <= (10^4 - 1)^2 * min(self.m_digits.size(), other.m_digits.size()) holds.
// In addition, since self.m_digits.size() + other.m_digits.size() <= 2^25 + 1, c_i <= (10^4 - 1)^2 * 2^24 = 1677386072457216 holds eventually.
// 1677386072457216 < 167772161 * 469762049 = 78812994116517889 holds, so we can reconstruct c_i from mod(c_i, 167772161) and mod(c_i, 469762049) by CRT.
long long c_i = tools::garner2(c1[i], c2[i]);
c_i += carry;
carry = c_i / BASE;
c_i %= BASE;
self.m_digits.push_back(c_i);
}
if (carry > 0) {
self.m_digits.push_back(carry);
}
self.m_nonnegative = self.m_nonnegative == other.m_nonnegative;
self.template regularize<0>();
return std::forward<decltype(self)>(self);
}
tools::bigint operator*(this auto&& lhs, const tools::bigint& rhs) {
return tools::bigint(std::forward<decltype(lhs)>(lhs)) *= rhs;
}
auto operator/=(this tools::mutable_type auto&& self, const tools::bigint& other) -> decltype(self) {
self = self / other;
return std::forward<decltype(self)>(self);
}
friend tools::bigint operator/(const tools::bigint& lhs, const tools::bigint& rhs) {
return lhs.divmod(rhs).first;
}
auto operator%=(this tools::mutable_type auto&& self, const tools::bigint& other) -> decltype(self) {
self = self % other;
return std::forward<decltype(self)>(self);
}
friend tools::bigint operator%(const tools::bigint& lhs, const tools::bigint& rhs) {
return lhs.divmod(rhs).second;
}
explicit operator bool() const {
return !this->m_digits.empty();
}
template <tools::non_bool_integral T>
explicit operator T() const {
assert(tools::bigint(std::numeric_limits<T>::min()) <= *this && *this <= tools::bigint(std::numeric_limits<T>::max()));
T result = 0;
for (std::size_t i = this->m_digits.size(); i --> 0;) {
result = result * BASE + this->m_digits[i] * (this->m_nonnegative ? 1 : -1);
}
return result;
}
explicit operator double() const {
long double result = 0.0;
const std::size_t precision = this->size();
for (std::size_t i = 0; i < std::numeric_limits<long double>::digits10; ++i) {
result = result * 10.0L + (precision >= i + 1 ? (*this)[precision - 1 - i] : 0) * tools::signum(*this);
}
result *= std::pow(10.0L, static_cast<long double>(precision) - static_cast<long double>(std::numeric_limits<long double>::digits10));
return static_cast<double>(result);
}
friend std::istream& operator>>(std::istream& is, tools::bigint& self) {
std::string s;
is >> s;
self = tools::bigint(s);
return is;
}
friend std::ostream& operator<<(std::ostream& os, const tools::bigint& self) {
if (!self.m_nonnegative) {
os << '-';
}
if (self.m_digits.empty()) {
return os << '0';
}
os << self.m_digits.back();
for (std::size_t i = 1; i < self.m_digits.size(); ++i) {
os << std::setw(LOG10_BASE) << std::setfill('0') << self.m_digits[self.m_digits.size() - 1 - i];
}
return os;
}
friend tools::detail::extgcd::impl<tools::bigint, tools::bigint>;
friend tools::detail::gcd::impl<tools::bigint, tools::bigint>;
friend tools::detail::signum::impl<tools::bigint>;
};
struct detail::gcd::impl<tools::bigint, tools::bigint>::mat22 {
tools::bigint a00, a01, a10, a11;
};
tools::bigint detail::abs::impl<tools::bigint>::operator()(auto&& x) const {
return tools::bigint(std::forward<decltype(x)>(x)).abs_inplace();
};
std::tuple<tools::bigint, tools::bigint, tools::bigint> detail::extgcd::impl<tools::bigint, tools::bigint>::operator()(tools::bigint a, tools::bigint b) const {
const bool a_neg = !a.m_nonnegative;
const bool b_neg = !b.m_nonnegative;
a.abs_inplace();
b.abs_inplace();
// Track cumulative matrix M: [a, b]^T = M * [|a_orig|, |b_orig|]^T
tools::bigint m00(1), m01(0), m10(0), m11(1);
if (tools::bigint::compare_3way_abs(a, b) < 0) {
std::swap(a, b);
std::swap(m00, m10);
std::swap(m01, m11);
}
while (!b.m_digits.empty()) {
if (a.m_digits.size() <= 64) {
while (!b.m_digits.empty()) {
auto [q, r] = a.divmod(b);
a = std::move(b);
b = std::move(r);
auto new_m10 = std::move(m00) - q * m10;
auto new_m11 = std::move(m01) - q * m11;
m00 = std::move(m10);
m01 = std::move(m11);
m10 = std::move(new_m10);
m11 = std::move(new_m11);
}
break;
}
auto R = tools::detail::gcd::impl<tools::bigint, tools::bigint>::half_gcd(a, b);
{
auto new_m00 = R.a00 * m00 + R.a01 * m10;
auto new_m01 = R.a00 * m01 + R.a01 * m11;
auto new_m10 = R.a10 * m00 + R.a11 * m10;
auto new_m11 = R.a10 * m01 + R.a11 * m11;
m00 = std::move(new_m00);
m01 = std::move(new_m01);
m10 = std::move(new_m10);
m11 = std::move(new_m11);
}
if (b.m_digits.empty()) break;
if (tools::bigint::compare_3way_abs(a, b) < 0) {
std::swap(a, b);
std::swap(m00, m10);
std::swap(m01, m11);
}
{
auto [q, r] = a.divmod(b);
a = std::move(b);
b = std::move(r);
auto new_m10 = std::move(m00) - q * m10;
auto new_m11 = std::move(m01) - q * m11;
m00 = std::move(m10);
m01 = std::move(m11);
m10 = std::move(new_m10);
m11 = std::move(new_m11);
}
}
// m00 * |a_orig| + m01 * |b_orig| = gcd (first row)
// m10 * |a_orig| + m11 * |b_orig| = 0 (second row)
// From second row: b' = |b_orig|/gcd = |m10|, a' = |a_orig|/gcd = |m11|
// Normalize m00 to [-b'/2, b'/2] for canonical (minimal) coefficients
if (!a.m_digits.empty()) {
auto b_prime = tools::abs(m10);
if (b_prime > tools::bigint(1)) {
auto a_prime = tools::abs(m11);
// Centered reduction: m00 mod b_prime in [-b_prime/2, b_prime/2]
auto r = m00 % b_prime;
if (!r.m_nonnegative) r += b_prime;
if (r * tools::bigint(2) > b_prime) r -= b_prime;
m00 = std::move(r);
// Recompute m01 from Bezout: m00*a' + m01*b' = 1
m01 = (tools::bigint(1) - m00 * a_prime) / b_prime;
}
}
// Adjust signs for original inputs
if (a_neg) m00.negate();
if (b_neg) m01.negate();
return std::make_tuple(std::move(m00), std::move(m01), std::move(a));
};
auto detail::gcd::impl<tools::bigint, tools::bigint>::half_gcd(tools::bigint& a, tools::bigint& b) -> mat22 {
const std::size_t n = a.m_digits.size();
const std::size_t m = n / 2;
if (b.m_digits.empty() || b.m_digits.size() <= m) {
return {tools::bigint(1), tools::bigint(0), tools::bigint(0), tools::bigint(1)};
}
if (n <= 64) {
mat22 R = {tools::bigint(1), tools::bigint(0), tools::bigint(0), tools::bigint(1)};
while (!b.m_digits.empty() && b.m_digits.size() > m) {
auto [q, r] = a.divmod(b);
a = std::move(b);
b = std::move(r);
auto new_a10 = std::move(R.a00) - q * R.a10;
auto new_a11 = std::move(R.a01) - q * R.a11;
R.a00 = std::move(R.a10);
R.a01 = std::move(R.a11);
R.a10 = std::move(new_a10);
R.a11 = std::move(new_a11);
}
return R;
}
// First recursive call on top halves
auto a1 = a.rshift(m);
auto b1 = b.rshift(m);
auto R = half_gcd(a1, b1);
// Apply R to full (a, b)
{
auto na = R.a00 * a + R.a01 * b;
auto nb = R.a10 * a + R.a11 * b;
a = std::move(na);
b = std::move(nb);
}
if (!a.m_nonnegative) { a.negate(); R.a00.negate(); R.a01.negate(); }
if (!b.m_nonnegative) { b.negate(); R.a10.negate(); R.a11.negate(); }
if (tools::bigint::compare_3way_abs(a, b) < 0) {
std::swap(a, b);
std::swap(R.a00, R.a10);
std::swap(R.a01, R.a11);
}
if (b.m_digits.empty() || b.m_digits.size() <= m) {
return R;
}
// Euclidean step
{
auto [q, r] = a.divmod(b);
a = std::move(b);
b = std::move(r);
auto new_a10 = std::move(R.a00) - q * R.a10;
auto new_a11 = std::move(R.a01) - q * R.a11;
R.a00 = std::move(R.a10);
R.a01 = std::move(R.a11);
R.a10 = std::move(new_a10);
R.a11 = std::move(new_a11);
}
if (b.m_digits.empty() || b.m_digits.size() <= m) {
return R;
}
// Second recursive call on top halves (adjusted shift)
const std::size_t l = a.m_digits.size();
const std::size_t k = (2 * m >= l) ? (2 * m - l) : 0;
auto a2 = a.rshift(k);
auto b2 = b.rshift(k);
auto R2 = half_gcd(a2, b2);
// Apply R2 to (a, b)
{
auto na = R2.a00 * a + R2.a01 * b;
auto nb = R2.a10 * a + R2.a11 * b;
a = std::move(na);
b = std::move(nb);
}
if (!a.m_nonnegative) { a.negate(); R2.a00.negate(); R2.a01.negate(); }
if (!b.m_nonnegative) { b.negate(); R2.a10.negate(); R2.a11.negate(); }
if (tools::bigint::compare_3way_abs(a, b) < 0) {
std::swap(a, b);
std::swap(R2.a00, R2.a10);
std::swap(R2.a01, R2.a11);
}
// Combine R2 * R
return {
R2.a00 * R.a00 + R2.a01 * R.a10,
R2.a00 * R.a01 + R2.a01 * R.a11,
R2.a10 * R.a00 + R2.a11 * R.a10,
R2.a10 * R.a01 + R2.a11 * R.a11
};
}
tools::bigint detail::gcd::impl<tools::bigint, tools::bigint>::operator()(tools::bigint a, tools::bigint b) const {
a.abs_inplace();
b.abs_inplace();
if (tools::bigint::compare_3way_abs(a, b) < 0) std::swap(a, b);
while (!b.m_digits.empty()) {
if (a.m_digits.size() <= 64) {
while (!b.m_digits.empty()) {
a %= b;
std::swap(a, b);
}
break;
}
half_gcd(a, b);
if (b.m_digits.empty()) break;
if (tools::bigint::compare_3way_abs(a, b) < 0) std::swap(a, b);
auto [q, r] = a.divmod(b);
a = std::move(b);
b = std::move(r);
}
return a;
};
int detail::signum::impl<tools::bigint>::operator()(const tools::bigint& x) const {
if (!x.m_nonnegative) return -1;
if (x.m_digits.empty()) return 0;
return 1;
};
}
#line 1 "tools/monoids.hpp"
#line 1 "tools/arithmetic.hpp"
#line 6 "tools/arithmetic.hpp"
namespace tools {
template <typename T>
concept arithmetic = tools::integral<T> || std::floating_point<T>;
}
#line 14 "tools/monoids.hpp"
namespace tools {
namespace monoids {
template <typename M>
struct bit_and {
using T = M;
static T op(const T& x, const T& y) {
return x & y;
}
static T e() {
return std::numeric_limits<T>::max();
}
};
template <typename M>
struct bit_or {
using T = M;
static T op(const T& x, const T& y) {
return x | y;
}
static T e() {
return T(0);
}
};
template <typename M>
requires requires (M x, M y) {
{tools::gcd(x, y)} -> std::convertible_to<M>;
}
struct gcd {
using T = M;
static T op(const T& x, const T& y) {
return tools::gcd(x, y);
}
static T e() {
return T(0);
}
};
template <typename M, M ...dummy>
struct max;
template <tools::arithmetic M>
struct max<M> {
using T = M;
static T op(const T& x, const T& y) {
return std::max(x, y);
}
static T e() {
if constexpr (tools::integral<M>) {
return std::numeric_limits<M>::min();
} else {
return -std::numeric_limits<M>::infinity();
}
}
};
template <std::totally_ordered M, M E>
struct max<M, E> {
using T = M;
static T op(const T& x, const T& y) {
assert(E <= x);
assert(E <= y);
return std::max(x, y);
}
static T e() {
return E;
}
};
template <typename M, M ...dummy>
struct min;
template <tools::arithmetic M>
struct min<M> {
using T = M;
static T op(const T& x, const T& y) {
return std::min(x, y);
}
static T e() {
if constexpr (tools::integral<M>) {
return std::numeric_limits<M>::max();
} else {
return std::numeric_limits<M>::infinity();
}
}
};
template <std::totally_ordered M, M E>
struct min<M, E> {
using T = M;
static T op(const T& x, const T& y) {
assert(x <= E);
assert(y <= E);
return std::min(x, y);
}
static T e() {
return E;
}
};
template <typename M>
struct multiplies {
using T = M;
static T op(const T& x, const T& y) {
return x * y;
}
static T e() {
return T(1);
}
};
template <>
struct multiplies<bool> {
using T = bool;
static T op(const bool x, const bool y) {
return x && y;
}
static T e() {
return true;
}
};
template <typename M, M E>
struct update {
using T = M;
static T op(const T& x, const T& y) {
return x == E ? y : x;
}
static T e() {
return E;
}
};
}
}
#line 11 "tests/monoids.test.cpp"
using mint = atcoder::modint998244353;
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
assert_that(tools::monoids::bit_and<bool>::op(false, true) == false);
assert_that(tools::monoids::bit_and<bool>::e() == true);
assert_that(tools::monoids::bit_and<short>::op(3, 5) == 1);
assert_that(tools::monoids::bit_and<short>::e() == std::numeric_limits<short>::max());
assert_that(tools::monoids::bit_and<unsigned short>::op(3U, 5U) == 1U);
assert_that(tools::monoids::bit_and<unsigned short>::e() == std::numeric_limits<unsigned short>::max());
assert_that(tools::monoids::bit_and<int>::op(3, 5) == 1);
assert_that(tools::monoids::bit_and<int>::e() == std::numeric_limits<int>::max());
assert_that(tools::monoids::bit_and<unsigned int>::op(3U, 5U) == 1U);
assert_that(tools::monoids::bit_and<unsigned int>::e() == std::numeric_limits<unsigned int>::max());
assert_that(tools::monoids::bit_and<long>::op(3L, 5L) == 1L);
assert_that(tools::monoids::bit_and<long>::e() == std::numeric_limits<long>::max());
assert_that(tools::monoids::bit_and<unsigned long>::op(3UL, 5UL) == 1UL);
assert_that(tools::monoids::bit_and<unsigned long>::e() == std::numeric_limits<unsigned long>::max());
assert_that(tools::monoids::bit_and<long long>::op(3LL, 5LL) == 1LL);
assert_that(tools::monoids::bit_and<long long>::e() == std::numeric_limits<long long>::max());
assert_that(tools::monoids::bit_and<unsigned long long>::op(3ULL, 5ULL) == 1ULL);
assert_that(tools::monoids::bit_and<unsigned long long>::e() == std::numeric_limits<unsigned long long>::max());
assert_that(tools::monoids::bit_and<tools::int128_t>::op(INT128_C(3), INT128_C(5)) == INT128_C(1));
assert_that(tools::monoids::bit_and<tools::int128_t>::e() == std::numeric_limits<tools::int128_t>::max());
assert_that(tools::monoids::bit_and<tools::uint128_t>::op(UINT128_C(3), UINT128_C(5)) == UINT128_C(1));
assert_that(tools::monoids::bit_and<tools::uint128_t>::e() == std::numeric_limits<tools::uint128_t>::max());
assert_that(tools::monoids::bit_or<bool>::op(false, true) == true);
assert_that(tools::monoids::bit_or<bool>::e() == false);
assert_that(tools::monoids::bit_or<short>::op(3, 5) == 7);
assert_that(tools::monoids::bit_or<short>::e() == 0);
assert_that(tools::monoids::bit_or<unsigned short>::op(3U, 5U) == 7U);
assert_that(tools::monoids::bit_or<unsigned short>::e() == 0U);
assert_that(tools::monoids::bit_or<int>::op(3, 5) == 7);
assert_that(tools::monoids::bit_or<int>::e() == 0);
assert_that(tools::monoids::bit_or<unsigned int>::op(3U, 5U) == 7U);
assert_that(tools::monoids::bit_or<unsigned int>::e() == 0U);
assert_that(tools::monoids::bit_or<long>::op(3L, 5L) == 7L);
assert_that(tools::monoids::bit_or<long>::e() == 0L);
assert_that(tools::monoids::bit_or<unsigned long>::op(3UL, 5UL) == 7UL);
assert_that(tools::monoids::bit_or<unsigned long>::e() == 0UL);
assert_that(tools::monoids::bit_or<long long>::op(3LL, 5LL) == 7LL);
assert_that(tools::monoids::bit_or<long long>::e() == 0LL);
assert_that(tools::monoids::bit_or<unsigned long long>::op(3ULL, 5ULL) == 7ULL);
assert_that(tools::monoids::bit_or<unsigned long long>::e() == 0ULL);
assert_that(tools::monoids::bit_or<tools::int128_t>::op(INT128_C(3), INT128_C(5)) == INT128_C(7));
assert_that(tools::monoids::bit_or<tools::int128_t>::e() == INT128_C(0));
assert_that(tools::monoids::bit_or<tools::uint128_t>::op(UINT128_C(3), UINT128_C(5)) == UINT128_C(7));
assert_that(tools::monoids::bit_or<tools::uint128_t>::e() == UINT128_C(0));
assert_that(tools::monoids::gcd<short>::op(-12, 18) == 6);
assert_that(tools::monoids::gcd<short>::e() == 0);
assert_that(tools::monoids::gcd<unsigned short>::op(12U, 18U) == 6U);
assert_that(tools::monoids::gcd<unsigned short>::e() == 0U);
assert_that(tools::monoids::gcd<int>::op(-12, 18) == 6);
assert_that(tools::monoids::gcd<int>::e() == 0);
assert_that(tools::monoids::gcd<unsigned int>::op(12U, 18U) == 6U);
assert_that(tools::monoids::gcd<unsigned int>::e() == 0U);
assert_that(tools::monoids::gcd<long>::op(-12L, 18L) == 6L);
assert_that(tools::monoids::gcd<long>::e() == 0L);
assert_that(tools::monoids::gcd<unsigned long>::op(12UL, 18UL) == 6UL);
assert_that(tools::monoids::gcd<unsigned long>::e() == 0UL);
assert_that(tools::monoids::gcd<long long>::op(-12LL, 18LL) == 6LL);
assert_that(tools::monoids::gcd<long long>::e() == 0LL);
assert_that(tools::monoids::gcd<unsigned long long>::op(12ULL, 18ULL) == 6ULL);
assert_that(tools::monoids::gcd<unsigned long long>::e() == 0ULL);
assert_that(tools::monoids::gcd<tools::int128_t>::op(INT128_C(-12), INT128_C(18)) == INT128_C(6));
assert_that(tools::monoids::gcd<tools::int128_t>::e() == INT128_C(0));
assert_that(tools::monoids::gcd<tools::uint128_t>::op(UINT128_C(12), UINT128_C(18)) == UINT128_C(6));
assert_that(tools::monoids::gcd<tools::uint128_t>::e() == UINT128_C(0));
assert_that(tools::monoids::gcd<tools::bigint>::op(tools::bigint(-12), tools::bigint(18)) == tools::bigint(6));
assert_that(tools::monoids::gcd<tools::bigint>::e() == tools::bigint(0));
assert_that(tools::monoids::max<bool>::op(false, true) == true);
assert_that(tools::monoids::max<bool>::e() == false);
assert_that(tools::monoids::max<char>::op('a', 'b') == 'b');
assert_that(tools::monoids::max<char>::e() == std::numeric_limits<char>::min());
assert_that(tools::monoids::max<short>::op(-1, 1) == 1);
assert_that(tools::monoids::max<short>::e() == std::numeric_limits<short>::min());
assert_that(tools::monoids::max<unsigned short>::op(0U, 1U) == 1U);
assert_that(tools::monoids::max<unsigned short>::e() == 0U);
assert_that(tools::monoids::max<int>::op(-1, 1) == 1);
assert_that(tools::monoids::max<int>::e() == std::numeric_limits<int>::min());
assert_that(tools::monoids::max<unsigned int>::op(0U, 1U) == 1U);
assert_that(tools::monoids::max<unsigned int>::e() == 0U);
assert_that(tools::monoids::max<long>::op(-1L, 1L) == 1L);
assert_that(tools::monoids::max<long>::e() == std::numeric_limits<long>::min());
assert_that(tools::monoids::max<unsigned long>::op(0UL, 1UL) == 1UL);
assert_that(tools::monoids::max<unsigned long>::e() == 0UL);
assert_that(tools::monoids::max<long long>::op(-1LL, 1LL) == 1LL);
assert_that(tools::monoids::max<long long>::e() == std::numeric_limits<long long>::min());
assert_that(tools::monoids::max<unsigned long long>::op(0ULL, 1ULL) == 1ULL);
assert_that(tools::monoids::max<unsigned long long>::e() == 0ULL);
assert_that(tools::monoids::max<float>::op(-1.0F, 1.0F) == 1.0F);
assert_that(tools::monoids::max<float>::e() == -std::numeric_limits<float>::infinity());
assert_that(tools::monoids::max<double>::op(-1.0, 1.0) == 1.0);
assert_that(tools::monoids::max<double>::e() == -std::numeric_limits<double>::infinity());
assert_that(tools::monoids::max<long double>::op(-1.0L, 1.0L) == 1.0L);
assert_that(tools::monoids::max<long double>::e() == -std::numeric_limits<long double>::infinity());
assert_that(tools::monoids::max<tools::int128_t>::op(INT128_C(-1), INT128_C(1)) == INT128_C(1));
assert_that(tools::monoids::max<tools::int128_t>::e() == std::numeric_limits<tools::int128_t>::min());
assert_that(tools::monoids::max<tools::uint128_t>::op(UINT128_C(0), UINT128_C(1)) == UINT128_C(1));
assert_that(tools::monoids::max<tools::uint128_t>::e() == UINT128_C(0));
assert_that(tools::monoids::max<int, 42>::op(42, 43) == 43);
assert_that(tools::monoids::max<int, 42>::e() == 42);
assert_that(tools::monoids::min<bool>::op(false, true) == false);
assert_that(tools::monoids::min<bool>::e() == true);
assert_that(tools::monoids::min<char>::op('a', 'b') == 'a');
assert_that(tools::monoids::min<char>::e() == std::numeric_limits<char>::max());
assert_that(tools::monoids::min<short>::op(-1, 1) == -1);
assert_that(tools::monoids::min<short>::e() == std::numeric_limits<short>::max());
assert_that(tools::monoids::min<unsigned short>::op(0U, 1U) == 0U);
assert_that(tools::monoids::min<unsigned short>::e() == std::numeric_limits<unsigned short>::max());
assert_that(tools::monoids::min<int>::op(-1, 1) == -1);
assert_that(tools::monoids::min<int>::e() == std::numeric_limits<int>::max());
assert_that(tools::monoids::min<unsigned int>::op(0U, 1U) == 0U);
assert_that(tools::monoids::min<unsigned int>::e() == std::numeric_limits<unsigned int>::max());
assert_that(tools::monoids::min<long>::op(-1L, 1L) == -1L);
assert_that(tools::monoids::min<long>::e() == std::numeric_limits<long>::max());
assert_that(tools::monoids::min<unsigned long>::op(0UL, 1UL) == 0UL);
assert_that(tools::monoids::min<unsigned long>::e() == std::numeric_limits<unsigned long>::max());
assert_that(tools::monoids::min<long long>::op(-1LL, 1LL) == -1LL);
assert_that(tools::monoids::min<long long>::e() == std::numeric_limits<long long>::max());
assert_that(tools::monoids::min<unsigned long long>::op(0ULL, 1ULL) == 0ULL);
assert_that(tools::monoids::min<unsigned long long>::e() == std::numeric_limits<unsigned long long>::max());
assert_that(tools::monoids::min<float>::op(-1.0F, 1.0F) == -1.0F);
assert_that(tools::monoids::min<float>::e() == std::numeric_limits<float>::infinity());
assert_that(tools::monoids::min<double>::op(-1.0, 1.0) == -1.0);
assert_that(tools::monoids::min<double>::e() == std::numeric_limits<double>::infinity());
assert_that(tools::monoids::min<long double>::op(-1.0L, 1.0L) == -1.0L);
assert_that(tools::monoids::min<long double>::e() == std::numeric_limits<long double>::infinity());
assert_that(tools::monoids::min<tools::int128_t>::op(INT128_C(-1), INT128_C(1)) == INT128_C(-1));
assert_that(tools::monoids::min<tools::int128_t>::e() == std::numeric_limits<tools::int128_t>::max());
assert_that(tools::monoids::min<tools::uint128_t>::op(UINT128_C(0), UINT128_C(1)) == UINT128_C(0));
assert_that(tools::monoids::min<tools::uint128_t>::e() == std::numeric_limits<tools::uint128_t>::max());
assert_that(tools::monoids::min<int, 42>::op(41, 42) == 41);
assert_that(tools::monoids::min<int, 42>::e() == 42);
assert_that(tools::monoids::multiplies<bool>::op(false, true) == false);
assert_that(tools::monoids::multiplies<bool>::e() == true);
assert_that(tools::monoids::multiplies<short>::op(-2, 3) == -6);
assert_that(tools::monoids::multiplies<short>::e() == 1);
assert_that(tools::monoids::multiplies<unsigned short>::op(2U, 3U) == 6U);
assert_that(tools::monoids::multiplies<unsigned short>::e() == 1U);
assert_that(tools::monoids::multiplies<int>::op(-2, 3) == -6);
assert_that(tools::monoids::multiplies<int>::e() == 1);
assert_that(tools::monoids::multiplies<unsigned int>::op(2U, 3U) == 6U);
assert_that(tools::monoids::multiplies<unsigned int>::e() == 1U);
assert_that(tools::monoids::multiplies<long>::op(-2L, 3L) == -6L);
assert_that(tools::monoids::multiplies<long>::e() == 1L);
assert_that(tools::monoids::multiplies<unsigned long>::op(2UL, 3UL) == 6UL);
assert_that(tools::monoids::multiplies<unsigned long>::e() == 1UL);
assert_that(tools::monoids::multiplies<long long>::op(-2LL, 3LL) == -6LL);
assert_that(tools::monoids::multiplies<long long>::e() == 1LL);
assert_that(tools::monoids::multiplies<unsigned long long>::op(2ULL, 3ULL) == 6ULL);
assert_that(tools::monoids::multiplies<unsigned long long>::e() == 1ULL);
assert_that(tools::monoids::multiplies<float>::op(-2.0F, 3.0F) == -6.0F);
assert_that(tools::monoids::multiplies<float>::e() == 1.0F);
assert_that(tools::monoids::multiplies<double>::op(-2.0, 3.0) == -6.0);
assert_that(tools::monoids::multiplies<double>::e() == 1.0);
assert_that(tools::monoids::multiplies<long double>::op(-2.0L, 3.0L) == -6.0L);
assert_that(tools::monoids::multiplies<long double>::e() == 1.0L);
assert_that(tools::monoids::multiplies<mint>::op(mint::raw(2), mint::raw(3)) == mint::raw(6));
assert_that(tools::monoids::multiplies<mint>::e() == mint::raw(1));
assert_that(tools::monoids::multiplies<tools::int128_t>::op(INT128_C(-2), INT128_C(3)) == INT128_C(-6));
assert_that(tools::monoids::multiplies<tools::int128_t>::e() == INT128_C(1));
assert_that(tools::monoids::multiplies<tools::uint128_t>::op(UINT128_C(2), UINT128_C(3)) == UINT128_C(6));
assert_that(tools::monoids::multiplies<tools::uint128_t>::e() == UINT128_C(1));
assert_that(tools::monoids::multiplies<tools::bigint>::op(tools::bigint(-2), tools::bigint(3)) == tools::bigint(-6));
assert_that(tools::monoids::multiplies<tools::bigint>::e() == tools::bigint(1));
assert_that(tools::monoids::update<bool, false>::op(true, false) == true);
assert_that(tools::monoids::update<bool, false>::op(false, true) == true);
assert_that(tools::monoids::update<bool, false>::e() == false);
assert_that(tools::monoids::update<char, '\0'>::op('a', 'b') == 'a');
assert_that(tools::monoids::update<char, '\0'>::op('\0', 'b') == 'b');
assert_that(tools::monoids::update<char, '\0'>::e() == '\0');
assert_that(tools::monoids::update<short, 42>::op(-1, 1) == -1);
assert_that(tools::monoids::update<short, 42>::op(42, 1) == 1);
assert_that(tools::monoids::update<short, 42>::e() == 42);
assert_that(tools::monoids::update<unsigned short, 42U>::op(0U, 1U) == 0U);
assert_that(tools::monoids::update<unsigned short, 42U>::op(42U, 1U) == 1U);
assert_that(tools::monoids::update<unsigned short, 42U>::e() == 42U);
assert_that(tools::monoids::update<int, 42>::op(-1, 1) == -1);
assert_that(tools::monoids::update<int, 42>::op(42, 1) == 1);
assert_that(tools::monoids::update<int, 42>::e() == 42);
assert_that(tools::monoids::update<unsigned int, 42U>::op(0U, 1U) == 0U);
assert_that(tools::monoids::update<unsigned int, 42U>::op(42U, 1U) == 1U);
assert_that(tools::monoids::update<unsigned int, 42U>::e() == 42U);
assert_that(tools::monoids::update<long, 42L>::op(-1L, 1L) == -1L);
assert_that(tools::monoids::update<long, 42L>::op(42L, 1L) == 1L);
assert_that(tools::monoids::update<long, 42L>::e() == 42L);
assert_that(tools::monoids::update<unsigned long, 42UL>::op(0UL, 1UL) == 0UL);
assert_that(tools::monoids::update<unsigned long, 42UL>::op(42UL, 1UL) == 1UL);
assert_that(tools::monoids::update<unsigned long, 42UL>::e() == 42UL);
assert_that(tools::monoids::update<long long, 42LL>::op(-1LL, 1LL) == -1LL);
assert_that(tools::monoids::update<long long, 42LL>::op(42LL, 1LL) == 1LL);
assert_that(tools::monoids::update<long long, 42LL>::e() == 42LL);
assert_that(tools::monoids::update<unsigned long long, 42ULL>::op(0ULL, 1ULL) == 0ULL);
assert_that(tools::monoids::update<unsigned long long, 42ULL>::op(42ULL, 1ULL) == 1ULL);
assert_that(tools::monoids::update<unsigned long long, 42ULL>::e() == 42ULL);
assert_that(tools::monoids::update<tools::int128_t, INT128_C(42)>::op(INT128_C(-1), INT128_C(1)) == INT128_C(-1));
assert_that(tools::monoids::update<tools::int128_t, INT128_C(42)>::op(INT128_C(42), INT128_C(1)) == INT128_C(1));
assert_that(tools::monoids::update<tools::int128_t, INT128_C(42)>::e() == INT128_C(42));
assert_that(tools::monoids::update<tools::uint128_t, UINT128_C(42)>::op(UINT128_C(0), UINT128_C(1)) == UINT128_C(0));
assert_that(tools::monoids::update<tools::uint128_t, UINT128_C(42)>::op(UINT128_C(42), UINT128_C(1)) == UINT128_C(1));
assert_that(tools::monoids::update<tools::uint128_t, UINT128_C(42)>::e() == UINT128_C(42));
return 0;
}