/* LICENSE.Nyaan
Creative Commons Legal Code
CC0 1.0 Universal
CREATIVE COMMONS CORPORATION IS NOT A LAW FIRM AND DOES NOT PROVIDE
LEGAL SERVICES. DISTRIBUTION OF THIS DOCUMENT DOES NOT CREATE AN
ATTORNEY-CLIENT RELATIONSHIP. CREATIVE COMMONS PROVIDES THIS
INFORMATION ON AN "AS-IS" BASIS. CREATIVE COMMONS MAKES NO WARRANTIES
REGARDING THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS
PROVIDED HEREUNDER, AND DISCLAIMS LIABILITY FOR DAMAGES RESULTING FROM
THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS PROVIDED
HEREUNDER.
Statement of Purpose
The laws of most jurisdictions throughout the world automatically confer
exclusive Copyright and Related Rights (defined below) upon the creator
and subsequent owner(s) (each and all, an "owner") of an original work of
authorship and/or a database (each, a "Work").
Certain owners wish to permanently relinquish those rights to a Work for
the purpose of contributing to a commons of creative, cultural and
scientific works ("Commons") that the public can reliably and without fear
of later claims of infringement build upon, modify, incorporate in other
works, reuse and redistribute as freely as possible in any form whatsoever
and for any purposes, including without limitation commercial purposes.
These owners may contribute to the Commons to promote the ideal of a free
culture and the further production of creative, cultural and scientific
works, or to gain reputation or greater distribution for their Work in
part through the use and efforts of others.
For these and/or other purposes and motivations, and without any
expectation of additional consideration or compensation, the person
associating CC0 with a Work (the "Affirmer"), to the extent that he or she
is an owner of Copyright and Related Rights in the Work, voluntarily
elects to apply CC0 to the Work and publicly distribute the Work under its
terms, with knowledge of his or her Copyright and Related Rights in the
Work and the meaning and intended legal effect of CC0 on those rights.
1. Copyright and Related Rights. A Work made available under CC0 may be
protected by copyright and related or neighboring rights ("Copyright and
Related Rights"). Copyright and Related Rights include, but are not
limited to, the following:
i. the right to reproduce, adapt, distribute, perform, display,
communicate, and translate a Work;
ii. moral rights retained by the original author(s) and/or performer(s);
iii. publicity and privacy rights pertaining to a person's image or
likeness depicted in a Work;
iv. rights protecting against unfair competition in regards to a Work,
subject to the limitations in paragraph 4(a), below;
v. rights protecting the extraction, dissemination, use and reuse of data
in a Work;
vi. database rights (such as those arising under Directive 96/9/EC of the
European Parliament and of the Council of 11 March 1996 on the legal
protection of databases, and under any national implementation
thereof, including any amended or successor version of such
directive); and
vii. other similar, equivalent or corresponding rights throughout the
world based on applicable law or treaty, and any national
implementations thereof.
2. Waiver. To the greatest extent permitted by, but not in contravention
of, applicable law, Affirmer hereby overtly, fully, permanently,
irrevocably and unconditionally waives, abandons, and surrenders all of
Affirmer's Copyright and Related Rights and associated claims and causes
of action, whether now known or unknown (including existing as well as
future claims and causes of action), in the Work (i) in all territories
worldwide, (ii) for the maximum duration provided by applicable law or
treaty (including future time extensions), (iii) in any current or future
medium and for any number of copies, and (iv) for any purpose whatsoever,
including without limitation commercial, advertising or promotional
purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each
member of the public at large and to the detriment of Affirmer's heirs and
successors, fully intending that such Waiver shall not be subject to
revocation, rescission, cancellation, termination, or any other legal or
equitable action to disrupt the quiet enjoyment of the Work by the public
as contemplated by Affirmer's express Statement of Purpose.
3. Public License Fallback. Should any part of the Waiver for any reason
be judged legally invalid or ineffective under applicable law, then the
Waiver shall be preserved to the maximum extent permitted taking into
account Affirmer's express Statement of Purpose. In addition, to the
extent the Waiver is so judged Affirmer hereby grants to each affected
person a royalty-free, non transferable, non sublicensable, non exclusive,
irrevocable and unconditional license to exercise Affirmer's Copyright and
Related Rights in the Work (i) in all territories worldwide, (ii) for the
maximum duration provided by applicable law or treaty (including future
time extensions), (iii) in any current or future medium and for any number
of copies, and (iv) for any purpose whatsoever, including without
limitation commercial, advertising or promotional purposes (the
"License"). The License shall be deemed effective as of the date CC0 was
applied by Affirmer to the Work. Should any part of the License for any
reason be judged legally invalid or ineffective under applicable law, such
partial invalidity or ineffectiveness shall not invalidate the remainder
of the License, and in such case Affirmer hereby affirms that he or she
will not (i) exercise any of his or her remaining Copyright and Related
Rights in the Work or (ii) assert any associated claims and causes of
action with respect to the Work, in either case contrary to Affirmer's
express Statement of Purpose.
4. Limitations and Disclaimers.
a. No trademark or patent rights held by Affirmer are waived, abandoned,
surrendered, licensed or otherwise affected by this document.
b. Affirmer offers the Work as-is and makes no representations or
warranties of any kind concerning the Work, express, implied,
statutory or otherwise, including without limitation warranties of
title, merchantability, fitness for a particular purpose, non
infringement, or the absence of latent or other defects, accuracy, or
the present or absence of errors, whether or not discoverable, all to
the greatest extent permissible under applicable law.
c. Affirmer disclaims responsibility for clearing rights of other persons
that may apply to the Work or any use thereof, including without
limitation any person's Copyright and Related Rights in the Work.
Further, Affirmer disclaims responsibility for obtaining any necessary
consents, permissions or other rights required for any use of the
Work.
d. Affirmer understands and acknowledges that Creative Commons is not a
party to this document and has no duty or obligation with respect to
this CC0 or use of the Work.
*/
// Begin public solver header: kernel.hpp
// Begin public solver header: ntt_large.hpp
// Canonical-residue adaptation permits mod < 2^31.
// Derived from NyaanNyaan/library (MIT), see LICENSE.Nyaan.
#include <bits/stdc++.h>
using namespace std;
template <uint32_t mod>
struct LazyMontgomeryModInt {
using mint = LazyMontgomeryModInt;
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(mod < (1u << 31), "invalid, mod >= 2 ^ 31");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
static_assert(r * mod == 1, "this code has bugs.");
u32 a;
constexpr LazyMontgomeryModInt() : a(0) {}
constexpr LazyMontgomeryModInt(const int64_t &b)
: a(reduce(u64(b % mod + mod) * n2)){};
static constexpr u32 reduce(const u64 &b) {
u32 ret = (b + u64(u32(b) * u32(-r)) * mod) >> 32; return ret >= mod ? ret - mod : ret;
}
constexpr mint &operator+=(const mint &b) {
a += b.a; if(a >= mod) a -= mod;
return *this;
}
constexpr mint &operator-=(const mint &b) {
a = a >= b.a ? a-b.a : a+mod-b.a;
return *this;
}
constexpr mint &operator*=(const mint &b) {
a = reduce(u64(a) * b.a);
return *this;
}
constexpr mint &operator/=(const mint &b) {
*this *= b.inverse();
return *this;
}
constexpr mint operator+(const mint &b) const { return mint(*this) += b; }
constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }
constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }
constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }
constexpr bool operator==(const mint &b) const {
return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
}
constexpr bool operator!=(const mint &b) const {
return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
}
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint operator+() const { return mint(*this); }
constexpr mint pow(u64 n) const {
mint ret(1), mul(*this);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
constexpr mint inverse() const { return pow(mod-2); }
friend ostream &operator<<(ostream &os, const mint &b) {
return os << b.get();
}
friend istream &operator>>(istream &is, mint &b) {
int64_t t;
is >> t;
b = LazyMontgomeryModInt<mod>(t);
return (is);
}
constexpr u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
static constexpr u32 get_mod() { return mod; }
};
#include <immintrin.h>
__attribute__((target("sse4.2"))) inline __m128i my128_mullo_epu32(
const __m128i &a, const __m128i &b) {
return _mm_mullo_epi32(a, b);
}
__attribute__((target("sse4.2"))) inline __m128i my128_mulhi_epu32(
const __m128i &a, const __m128i &b) {
__m128i a13 = _mm_shuffle_epi32(a, 0xF5);
__m128i b13 = _mm_shuffle_epi32(b, 0xF5);
__m128i prod02 = _mm_mul_epu32(a, b);
__m128i prod13 = _mm_mul_epu32(a13, b13);
__m128i prod = _mm_unpackhi_epi64(_mm_unpacklo_epi32(prod02, prod13),
_mm_unpackhi_epi32(prod02, prod13));
return prod;
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_mul_128(
const __m128i &a, const __m128i &b, const __m128i &r, const __m128i &m1) {
__m128i v=_mm_sub_epi32(_mm_add_epi32(my128_mulhi_epu32(a, b), m1), my128_mulhi_epu32(my128_mullo_epu32(my128_mullo_epu32(a,b), r),m1)); return _mm_min_epu32(v,_mm_sub_epi32(v,m1));
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_add_128(
const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
__m128i m1=_mm_srli_epi32(m2,1), v=_mm_add_epi32(a,b); return _mm_min_epu32(v,_mm_sub_epi32(v,m1));
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_sub_128(
const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
__m128i m1=_mm_srli_epi32(m2,1), v=_mm_sub_epi32(a,b); return _mm_min_epu32(v,_mm_add_epi32(v,m1));
}
__attribute__((target("avx2"))) inline __m256i my256_mullo_epu32(
const __m256i &a, const __m256i &b) {
return _mm256_mullo_epi32(a, b);
}
__attribute__((target("avx2"))) inline __m256i my256_mulhi_epu32(
const __m256i &a, const __m256i &b) {
__m256i a13 = _mm256_shuffle_epi32(a, 0xF5);
__m256i b13 = _mm256_shuffle_epi32(b, 0xF5);
__m256i prod02 = _mm256_mul_epu32(a, b);
__m256i prod13 = _mm256_mul_epu32(a13, b13);
__m256i prod = _mm256_unpackhi_epi64(_mm256_unpacklo_epi32(prod02, prod13),
_mm256_unpackhi_epi32(prod02, prod13));
return prod;
}
__attribute__((target("avx2"))) inline __m256i montgomery_mul_256(
const __m256i &a, const __m256i &b, const __m256i &r, const __m256i &m1) {
__m256i v=_mm256_sub_epi32(_mm256_add_epi32(my256_mulhi_epu32(a, b), m1), my256_mulhi_epu32(my256_mullo_epu32(my256_mullo_epu32(a,b), r),m1)); return _mm256_min_epu32(v,_mm256_sub_epi32(v,m1));
}
__attribute__((target("avx2"))) inline __m256i montgomery_add_256(
const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
__m256i m1=_mm256_srli_epi32(m2,1), v=_mm256_add_epi32(a,b); return _mm256_min_epu32(v,_mm256_sub_epi32(v,m1));
}
__attribute__((target("avx2"))) inline __m256i montgomery_sub_256(
const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
__m256i m1=_mm256_srli_epi32(m2,1), v=_mm256_sub_epi32(a,b); return _mm256_min_epu32(v,_mm256_add_epi32(v,m1));
}
namespace ntt_inner {
using u64 = uint64_t;
constexpr uint32_t get_pr(uint32_t mod) {
if (mod == 2) return 1;
u64 ds[32] = {};
int idx = 0;
u64 m = mod - 1;
for (u64 i = 2; i * i <= m; ++i) {
if (m % i == 0) {
ds[idx++] = i;
while (m % i == 0) m /= i;
}
}
if (m != 1) ds[idx++] = m;
uint32_t pr = 2;
while (1) {
int flg = 1;
for (int i = 0; i < idx; ++i) {
u64 a = pr, b = (mod - 1) / ds[i], r = 1;
while (b) {
if (b & 1) r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
if (r == 1) {
flg = 0;
break;
}
}
if (flg == 1) break;
++pr;
}
return pr;
}
constexpr int SZ_FFT_BUF = 1 << 25;
uint32_t _buf1[SZ_FFT_BUF] __attribute__((aligned(64)));
uint32_t _buf2[SZ_FFT_BUF] __attribute__((aligned(64)));
} // namespace ntt_inner
template <typename mint>
struct NTT {
static constexpr uint32_t mod = mint::get_mod();
static constexpr uint32_t pr = ntt_inner::get_pr(mint::get_mod());
static constexpr int level = __builtin_ctzll(mod - 1);
mint dw[level], dy[level];
mint *buf1, *buf2;
constexpr NTT() {
setwy(level);
union raw_cast {
mint dat;
uint32_t _;
};
buf1 = &(((raw_cast *)(ntt_inner::_buf1))->dat);
buf2 = &(((raw_cast *)(ntt_inner::_buf2))->dat);
}
constexpr void setwy(int k) {
mint w[level], y[level];
w[k - 1] = mint(pr).pow((mod - 1) / (1 << k));
y[k - 1] = w[k - 1].inverse();
for (int i = k - 2; i > 0; --i)
w[i] = w[i + 1] * w[i + 1], y[i] = y[i + 1] * y[i + 1];
dw[0] = dy[0] = w[1] * w[1];
dw[1] = w[1], dy[1] = y[1], dw[2] = w[2], dy[2] = y[2];
for (int i = 3; i < k; ++i) {
dw[i] = dw[i - 1] * y[i - 2] * w[i];
dy[i] = dy[i - 1] * w[i - 2] * y[i];
}
}
__attribute__((target("avx2"))) void ntt(mint *a, int n) {
int k = n ? __builtin_ctz(n) : 0;
if (k == 0) return;
if (k == 1) {
mint a1 = a[1];
a[1] = a[0] - a[1];
a[0] = a[0] + a1;
return;
}
if (k & 1) {
int v = 1 << (k - 1);
if (v < 8) {
for (int j = 0; j < v; ++j) {
mint ajv = a[j + v];
a[j + v] = a[j] - ajv;
a[j] += ajv;
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
int j0 = 0;
int j1 = v;
for (; j0 < v; j0 += 8, j1 += 8) {
__m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
__m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
__m256i naj = montgomery_add_256(T0, T1, m2, m0);
__m256i najv = montgomery_sub_256(T0, T1, m2, m0);
_mm256_storeu_si256((__m256i *)(a + j0), naj);
_mm256_storeu_si256((__m256i *)(a + j1), najv);
}
}
}
int u = 1 << (2 + (k & 1));
int v = 1 << (k - 2 - (k & 1));
mint one = mint(1);
mint imag = dw[1];
while (v) {
if (v == 1) {
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
ww = xx * xx, wx = ww * xx;
mint t0 = a[jh + 0], t1 = a[jh + 1] * xx;
mint t2 = a[jh + 2] * ww, t3 = a[jh + 3] * wx;
mint t0p2 = t0 + t2, t1p3 = t1 + t3;
mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag;
a[jh + 0] = t0p2 + t1p3, a[jh + 1] = t0p2 - t1p3;
a[jh + 2] = t0m2 + t1m3, a[jh + 3] = t0m2 - t1m3;
xx *= dw[__builtin_ctz((jh += 4))];
}
} else if (v == 4) {
const __m128i m0 = _mm_set1_epi32(0);
const __m128i m1 = _mm_set1_epi32(mod);
const __m128i m2 = _mm_set1_epi32(mod + mod);
const __m128i r = _mm_set1_epi32(mint::r);
const __m128i Imag = _mm_set1_epi32(imag.a);
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = v;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P2 = montgomery_add_128(T0, T2, m2, m0);
const __m128i T1P3 = montgomery_add_128(T1, T3, m2, m0);
const __m128i T0M2 = montgomery_sub_128(T0, T2, m2, m0);
const __m128i T1M3 = montgomery_mul_128(
montgomery_sub_128(T1, T3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_sub_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_add_128(T0M2, T1M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M2, T1M3, m2, m0));
}
} else {
ww = xx * xx, wx = ww * xx;
const __m128i WW = _mm_set1_epi32(ww.a);
const __m128i WX = _mm_set1_epi32(wx.a);
const __m128i XX = _mm_set1_epi32(xx.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i MT1 = montgomery_mul_128(T1, XX, r, m1);
const __m128i MT2 = montgomery_mul_128(T2, WW, r, m1);
const __m128i MT3 = montgomery_mul_128(T3, WX, r, m1);
const __m128i T0P2 = montgomery_add_128(T0, MT2, m2, m0);
const __m128i T1P3 = montgomery_add_128(MT1, MT3, m2, m0);
const __m128i T0M2 = montgomery_sub_128(T0, MT2, m2, m0);
const __m128i T1M3 = montgomery_mul_128(
montgomery_sub_128(MT1, MT3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_sub_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_add_128(T0M2, T1M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M2, T1M3, m2, m0));
}
}
xx *= dw[__builtin_ctz((jh += 4))];
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i Imag = _mm256_set1_epi32(imag.a);
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = v;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P2 = montgomery_add_256(T0, T2, m2, m0);
const __m256i T1P3 = montgomery_add_256(T1, T3, m2, m0);
const __m256i T0M2 = montgomery_sub_256(T0, T2, m2, m0);
const __m256i T1M3 = montgomery_mul_256(
montgomery_sub_256(T1, T3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_sub_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_add_256(T0M2, T1M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M2, T1M3, m2, m0));
}
} else {
ww = xx * xx, wx = ww * xx;
const __m256i WW = _mm256_set1_epi32(ww.a);
const __m256i WX = _mm256_set1_epi32(wx.a);
const __m256i XX = _mm256_set1_epi32(xx.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i MT1 = montgomery_mul_256(T1, XX, r, m1);
const __m256i MT2 = montgomery_mul_256(T2, WW, r, m1);
const __m256i MT3 = montgomery_mul_256(T3, WX, r, m1);
const __m256i T0P2 = montgomery_add_256(T0, MT2, m2, m0);
const __m256i T1P3 = montgomery_add_256(MT1, MT3, m2, m0);
const __m256i T0M2 = montgomery_sub_256(T0, MT2, m2, m0);
const __m256i T1M3 = montgomery_mul_256(
montgomery_sub_256(MT1, MT3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_sub_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_add_256(T0M2, T1M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M2, T1M3, m2, m0));
}
}
xx *= dw[__builtin_ctz((jh += 4))];
}
}
u <<= 2;
v >>= 2;
}
}
__attribute__((target("avx2"))) void intt(mint *a, int n,
int normalize = true) {
int k = n ? __builtin_ctz(n) : 0;
if (k == 0) return;
if (k == 1) {
mint a1 = a[1];
a[1] = a[0] - a[1];
a[0] = a[0] + a1;
if (normalize) {
a[0] *= mint(2).inverse();
a[1] *= mint(2).inverse();
}
return;
}
int u = 1 << (k - 2);
int v = 1;
mint one = mint(1);
mint imag = dy[1];
while (u) {
if (v == 1) {
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
ww = xx * xx, yy = xx * imag;
mint t0 = a[jh + 0], t1 = a[jh + 1];
mint t2 = a[jh + 2], t3 = a[jh + 3];
mint t0p1 = t0 + t1, t2p3 = t2 + t3;
mint t0m1 = (t0 - t1) * xx, t2m3 = (t2 - t3) * yy;
a[jh + 0] = t0p1 + t2p3, a[jh + 2] = (t0p1 - t2p3) * ww;
a[jh + 1] = t0m1 + t2m3, a[jh + 3] = (t0m1 - t2m3) * ww;
xx *= dy[__builtin_ctz(jh += 4)];
}
} else if (v == 4) {
const __m128i m0 = _mm_set1_epi32(0);
const __m128i m1 = _mm_set1_epi32(mod);
const __m128i m2 = _mm_set1_epi32(mod + mod);
const __m128i r = _mm_set1_epi32(mint::r);
const __m128i Imag = _mm_set1_epi32(imag.a);
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = v + v;
int j3 = j2 + v;
for (; j0 < v; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
const __m128i T0M1 = montgomery_sub_128(T0, T1, m2, m0);
const __m128i T2M3 = montgomery_mul_128(
montgomery_sub_128(T2, T3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_sub_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_add_128(T0M1, T2M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M1, T2M3, m2, m0));
}
} else {
ww = xx * xx, yy = xx * imag;
const __m128i WW = _mm_set1_epi32(ww.a);
const __m128i XX = _mm_set1_epi32(xx.a);
const __m128i YY = _mm_set1_epi32(yy.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
const __m128i T0M1 = montgomery_mul_128(
montgomery_sub_128(T0, T1, m2, m0), XX, r, m1);
__m128i T2M3 = montgomery_mul_128(
montgomery_sub_128(T2, T3, m2, m0), YY, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128(
(__m128i *)(a + j2),
montgomery_mul_128(montgomery_sub_128(T0P1, T2P3, m2, m0), WW,
r, m1));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_add_128(T0M1, T2M3, m2, m0));
_mm_storeu_si128(
(__m128i *)(a + j3),
montgomery_mul_128(montgomery_sub_128(T0M1, T2M3, m2, m0), WW,
r, m1));
}
}
xx *= dy[__builtin_ctz(jh += 4)];
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i Imag = _mm256_set1_epi32(imag.a);
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = v + v;
int j3 = j2 + v;
for (; j0 < v; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
const __m256i T0M1 = montgomery_sub_256(T0, T1, m2, m0);
const __m256i T2M3 = montgomery_mul_256(
montgomery_sub_256(T2, T3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_sub_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_add_256(T0M1, T2M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M1, T2M3, m2, m0));
}
} else {
ww = xx * xx, yy = xx * imag;
const __m256i WW = _mm256_set1_epi32(ww.a);
const __m256i XX = _mm256_set1_epi32(xx.a);
const __m256i YY = _mm256_set1_epi32(yy.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
const __m256i T0M1 = montgomery_mul_256(
montgomery_sub_256(T0, T1, m2, m0), XX, r, m1);
const __m256i T2M3 = montgomery_mul_256(
montgomery_sub_256(T2, T3, m2, m0), YY, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256(
(__m256i *)(a + j2),
montgomery_mul_256(montgomery_sub_256(T0P1, T2P3, m2, m0), WW,
r, m1));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_add_256(T0M1, T2M3, m2, m0));
_mm256_storeu_si256(
(__m256i *)(a + j3),
montgomery_mul_256(montgomery_sub_256(T0M1, T2M3, m2, m0), WW,
r, m1));
}
}
xx *= dy[__builtin_ctz(jh += 4)];
}
}
u >>= 4;
v <<= 2;
}
if (k & 1) {
v = 1 << (k - 1);
if (v < 8) {
for (int j = 0; j < v; ++j) {
mint ajv = a[j] - a[j + v];
a[j] += a[j + v];
a[j + v] = ajv;
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
int j0 = 0;
int j1 = v;
for (; j0 < v; j0 += 8, j1 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
__m256i naj = montgomery_add_256(T0, T1, m2, m0);
__m256i najv = montgomery_sub_256(T0, T1, m2, m0);
_mm256_storeu_si256((__m256i *)(a + j0), naj);
_mm256_storeu_si256((__m256i *)(a + j1), najv);
}
}
}
if (normalize) {
mint invn = mint(n).inverse();
for (int i = 0; i < n; i++) a[i] *= invn;
}
}
__attribute__((target("avx2"))) void inplace_multiply(
int l1, int l2, int zero_padding = true) {
int l = l1 + l2 - 1;
int M = 4;
while (M < l) M <<= 1;
if (zero_padding) {
for (int i = l1; i < M; i++) ntt_inner::_buf1[i] = 0;
for (int i = l2; i < M; i++) ntt_inner::_buf2[i] = 0;
}
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i N2 = _mm256_set1_epi32(mint::n2);
for (int i = 0; i < l1; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = montgomery_mul_256(a, N2, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), b);
}
for (int i = 0; i < l2; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
__m256i b = montgomery_mul_256(a, N2, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf2 + i), b);
}
ntt(buf1, M);
ntt(buf2, M);
for (int i = 0; i < M; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
__m256i c = montgomery_mul_256(a, b, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), c);
}
intt(buf1, M, false);
const __m256i INVM = _mm256_set1_epi32((mint(M).inverse()).a);
for (int i = 0; i < l; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = montgomery_mul_256(a, INVM, r, m1);
__m256i c = my256_mulhi_epu32(my256_mullo_epu32(b, r), m1);
__m256i d = _mm256_and_si256(_mm256_cmpgt_epi32(c, m0), m1);
__m256i e = _mm256_sub_epi32(d, c);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), e);
}
}
void ntt(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
ntt(buf1, M);
for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
}
void intt(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
intt(buf1, M, true);
for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
}
vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {
if (a.size() == 0 && b.size() == 0) return vector<mint>{};
int l = a.size() + b.size() - 1;
if (min<int>(a.size(), b.size()) <= 40) {
vector<mint> s(l);
for (int i = 0; i < (int)a.size(); ++i)
for (int j = 0; j < (int)b.size(); ++j) s[i + j] += a[i] * b[j];
return s;
}
assert(l <= ntt_inner::SZ_FFT_BUF);
int M = 4;
while (M < l) M <<= 1;
for (int i = 0; i < (int)a.size(); ++i) buf1[i].a = a[i].a;
for (int i = (int)a.size(); i < M; ++i) buf1[i].a = 0;
for (int i = 0; i < (int)b.size(); ++i) buf2[i].a = b[i].a;
for (int i = (int)b.size(); i < M; ++i) buf2[i].a = 0;
ntt(buf1, M);
ntt(buf2, M);
for (int i = 0; i < M; ++i)
buf1[i].a = mint::reduce(uint64_t(buf1[i].a) * buf2[i].a);
intt(buf1, M, false);
vector<mint> s(l);
mint invm = mint(M).inverse();
for (int i = 0; i < l; ++i) s[i] = buf1[i] * invm;
return s;
}
void ntt_doubling(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
intt(buf1, M);
mint r = 1, zeta = mint(pr).pow((mint::get_mod() - 1) / (M << 1));
for (int i = 0; i < M; i++) buf1[i] *= r, r *= zeta;
ntt(buf1, M);
a.resize(2 * M);
for (int i = 0; i < M; i++) a[M + i].a = buf1[i].a;
}
};
// End public solver header: ntt_large.hpp
namespace add_sub {
constexpr uint32_t P1=2013265921,P2=1811939329,P3=2113929217;
inline uint64_t modpow(uint64_t x,uint64_t n,uint64_t m){uint64_t y=1;for(;n;n>>=1,x=x*x%m)if(n&1)y=y*x%m;return y;}
template<uint32_t P> void residues(unsigned n,const unsigned*a,const unsigned*b,unsigned*r,unsigned off,unsigned count,bool reverse_b){
using Mint=LazyMontgomeryModInt<P>;static NTT<Mint>fft;
unsigned N=4;while(N<2*n-1)N<<=1;assert(N<=unsigned(ntt_inner::SZ_FFT_BUF));
for(unsigned i=0;i<n;++i){ntt_inner::_buf1[i]=a[i]%P;ntt_inner::_buf2[i]=b[reverse_b?n-1-i:i]%P;}
fft.inplace_multiply(n,n,true);
for(unsigned i=0;i<count;++i)r[i]=ntt_inner::_buf1[off+i];
}
inline void window(unsigned n,const unsigned*a,const unsigned*b,unsigned*c,unsigned off,unsigned count,bool reverse_b){
assert(n<=16777216&&uint64_t(off)+count<=2ull*n-1);std::vector<unsigned>x(count),y(count);
residues<P1>(n,a,b,x.data(),off,count,reverse_b);residues<P2>(n,a,b,y.data(),off,count,reverse_b);residues<P3>(n,a,b,c,off,count,reverse_b);
const uint64_t inv1=modpow(P1,P2-2,P2),p12=uint64_t(P1)*P2,inv12=modpow(p12%P3,P3-2,P3);
for(unsigned i=0;i<count;++i){uint64_t t=(y[i]+uint64_t(P2)-x[i]%P2)%P2*inv1%P2;uint64_t z=x[i]+uint64_t(P1)*t;uint64_t q=(c[i]+uint64_t(P3)-z%P3)%P3*inv12%P3;c[i]=uint32_t(z)+uint32_t(p12)*uint32_t(q);}
}
inline void base(unsigned n,const unsigned*a,const unsigned*b,unsigned*c,bool minus){window(n,a,b,c,minus?n-1:0,n,minus);}
inline void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c,bool minus){
if(n<=16777216){base(n,a,b,c,minus);return;}
// Exact overlap-add. All block products and their coefficient windows are exact.
const unsigned L=16777216;std::fill(c,c+n,0u);std::vector<unsigned>aa(L),bb(L),out(2*L);
const uint64_t lo=0,hi=n;
for(unsigned x=0;x<n;x+=L)for(unsigned y=0;y<n;y+=L){unsigned an=std::min(L,n-x),bn=std::min(L,n-y);uint64_t off=uint64_t(x)+y;
if(off>=hi||off+an+bn-1<=lo)continue;
unsigned len=std::max(an,bn);std::fill(aa.begin(),aa.begin()+len,0u);std::fill(bb.begin(),bb.begin()+len,0u);
for(unsigned i=0;i<an;++i)aa[i]=a[minus?n-1-x-i:x+i];for(unsigned j=0;j<bn;++j)bb[j]=b[y+j];
unsigned begin=unsigned(std::max(lo,off)-off),count=unsigned(std::min(hi,off+an+bn-1)-off-begin);
window(len,aa.data(),bb.data(),out.data(),begin,count,false);
unsigned dst=unsigned(off+begin-lo);for(unsigned k=0;k<count;++k)c[minus?n-1-dst-k:dst+k]+=out[k];
}
}
}
// End public solver header: kernel.hpp
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){add_sub::convolution(n,a,b,c,false);}