結果
問題 | No.2330 Eat Slime |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:45:59 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 975 ms / 4,000 ms |
コード長 | 45,384 bytes |
コンパイル時間 | 4,709 ms |
コンパイル使用メモリ | 95,544 KB |
実行使用メモリ | 74,448 KB |
最終ジャッジ日時 | 2024-12-27 08:35:31 |
合計ジャッジ時間 | 26,248 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
public class Main {public static void main(String[] args) {new Main();}public Main() {FastScanner fs = new FastScanner();java.io.PrintWriter out = new java.io.PrintWriter(System.out);solve(fs, out);out.flush();}public void solve(FastScanner fs, java.io.PrintWriter out) {int N = fs.nextInt(), M = fs.nextInt(), X = fs.nextInt();int[][] slime = new int[5][N];for (int i = 0;i < N;++ i) {int C = fs.nextInt() - 1;slime[C][i] = 1;}int[][] bonus = new int[5][N + 1];for (int i = 0;i < M;++ i) {int A = fs.nextInt() - 1, B = fs.nextInt() - 1, Y = fs.nextInt();bonus[B][N - A] += Y;}int[][] score = new int[5][];for (int i = 0;i < 5;++ i) score[i] = Convolution.convolution998_244_353(slime[i], bonus[i]);int ans = X * N;for (int i = 0;i < N;++ i) {int tmp = X * i;for (int j = 0;j < 5;++ j) tmp += score[j][N + i];ans = Math.max(ans, tmp);}out.println(ans);}final int MOD = 998_244_353;int plus(int n, int m) {int sum = n + m;if (sum >= MOD) sum -= MOD;return sum;}int minus(int n, int m) {int sum = n - m;if (sum < 0) sum += MOD;return sum;}int times(int n, int m) {return (int) ((long) n * m % MOD);}int divide(int n, int m) {return times(n, IntMath.pow(m, MOD - 2, MOD));}int[] fact, invf;void calc(int len) {len += 2;fact = new int[len];invf = new int[len];fact[0] = fact[1] = invf[0] = invf[1] = 1;for (int i = 2; i < fact.length; ++i) fact[i] = times(fact[i - 1], i);invf[len - 1] = divide(1, fact[len - 1]);for (int i = len - 1; i > 1; --i) invf[i - 1] = times(i, invf[i]);}int comb(int n, int m) {if (n < m) return 0;return times(fact[n], times(invf[n - m], invf[m]));}public static final class MathLib {public static class Barrett {private final int mod;private final long h, l;private final long MAX = 1L << 62;private final int MASK = (1 << 31) - 1;Barrett(final int mod) {this.mod = mod;final long t = MAX / mod;h = t >>> 31;l = t & MASK;}int reduce(final long x) {final long xh = x >>> 31, xl = x & MASK;long z = xl * l;z = xl * h + xh * l + (z >>> 31);z = xh * h + (z >>> 31);final int ret = (int) (x - z * mod);return ret >= mod ? ret - mod : ret;}}public static class BarrettSmall {private final int mod;final long t;BarrettSmall(final int mod) {this.mod = mod;t = (1L << 42) / mod;}int reduce(long x) {long q = x * t >> 42;x -= q * mod;return (int) (x >= mod ? x - mod : x);}}private static long safe_mod(long x, final long m) {x %= m;if (x < 0) x += m;return x;}private static long[] inv_gcd(long a, final long b) {a = safe_mod(a, b);if (a == 0) return new long[] { b, 0 };long s = b, t = a;long m0 = 0, m1 = 1;while (t > 0) {final long u = s / t;s -= t * u;m0 -= m1 * u;long tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}if (m0 < 0) m0 += b / s;return new long[] { s, m0 };}public static int pow(long n, long m, final int mod) {assert m >= 0 && mod >= 1;if (mod == 1) return 0;return pow(n, m, new Barrett(mod));}public static int pow(long n, long m, Barrett mod) {assert m >= 0;long ans = 1, num = n;while (m != 0) {if ((m & 1) != 0) ans = mod.reduce(ans * num);m >>>= 1;num = mod.reduce(num * num);}return (int) ans;}public static int pow998_244_353(long n, long m) {assert m >= 0;long ans = 1, num = n;while (m != 0) {if ((m & 1) != 0) ans = ans * num % 998_244_353;m >>>= 1;num = num * num % 998_244_353;}return (int) ans;}public static int pow754_974_721(long n, long m) {assert m >= 0;long ans = 1, num = n;while (m != 0) {if ((m & 1) != 0) ans = ans * num % 754_974_721;m >>>= 1;num = num * num % 754_974_721;}return (int) ans;}public static int pow167_772_161(long n, long m) {assert m >= 0;long ans = 1, num = n;while (m != 0) {if ((m & 1) != 0) ans = ans * num % 167_772_161;m >>>= 1;num = num * num % 167_772_161;}return (int) ans;}public static int pow469_762_049(long n, long m) {assert m >= 0;long ans = 1, num = n;while (m != 0) {if ((m & 1) != 0) ans = ans * num % 469_762_049;m >>>= 1;num = num * num % 469_762_049;}return (int) ans;}public static int pow1_000_000_007(long n, long m) {assert m >= 0;long ans = 1, num = n;while (m != 0) {if ((m & 1) != 0) ans = ans * num % 1_000_000_007;m >>>= 1;num = num * num % 1_000_000_007;}return (int) ans;}public static int pow(long n, long m, BarrettSmall mod) {assert m >= 0;long ans = 1, num = n;while (m != 0) {if ((m & 1) != 0) ans = mod.reduce(ans * num);m >>>= 1;num = mod.reduce(num * num);}return (int) ans;}public static long[] crt(final long[] r, final long[] m) {assert r.length == m.length;final int n = r.length;long r0 = 0, m0 = 1;for (int i = 0; i < n; i++) {assert 1 <= m[i];long r1 = safe_mod(r[i], m[i]), m1 = m[i];if (m0 < m1) {long tmp = r0;r0 = r1;r1 = tmp;tmp = m0;m0 = m1;m1 = tmp;}if (m0 % m1 == 0) {if (r0 % m1 != r1) return new long[] { 0, 0 };continue;}final long[] ig = inv_gcd(m0, m1);final long g = ig[0], im = ig[1];final long u1 = m1 / g;if ((r1 - r0) % g != 0) return new long[] { 0, 0 };final long x = (r1 - r0) / g % u1 * im % u1;r0 += x * m0;m0 *= u1;if (r0 < 0) r0 += m0;// System.err.printf("%d %d\n", r0, m0);}return new long[] { r0, m0 };}public static long floor_sum(final long n, final long m, long a, long b) {long ans = 0;if (a >= m) {ans += (n - 1) * n * (a / m) / 2;a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}final long y_max = (a * n + b) / m;final long x_max = y_max * m - b;if (y_max == 0) return ans;ans += (n - (x_max + a - 1) / a) * y_max;ans += floor_sum(y_max, a, m, (a - x_max % a) % a);return ans;}}/*** Convolution.** @verified https://atcoder.jp/contests/practice2/tasks/practice2_f* @verified https://judge.yosupo.jp/problem/convolution_mod_1000000007*/public static final class Convolution {/*** writer: amotama 勝手に借りてます、問題あったらごめんね*/private static void fft(double[] a, double[] b, boolean invert) {int count = a.length;for (int i = 1, j = 0; i < count; i++) {int bit = count >> 1;for (; j >= bit; bit >>= 1) {j -= bit;}j += bit;if (i < j) {double temp = a[i];a[i] = a[j];a[j] = temp;temp = b[i];b[i] = b[j];b[j] = temp;}}for (int len = 2; len <= count; len <<= 1) {int halfLen = len >> 1;double angle = 2 * Math.PI / len;if (invert) {angle = -angle;}double wLenA = Math.cos(angle);double wLenB = Math.sin(angle);for (int i = 0; i < count; i += len) {double wA = 1;double wB = 0;for (int j = 0; j < halfLen; j++) {double uA = a[i + j];double uB = b[i + j];double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;a[i + j] = uA + vA;b[i + j] = uB + vB;a[i + j + halfLen] = uA - vA;b[i + j + halfLen] = uB - vB;double nextWA = wA * wLenA - wB * wLenB;wB = wA * wLenB + wB * wLenA;wA = nextWA;}}}if (invert) {for (int i = 0; i < count; i++) {a[i] /= count;b[i] /= count;}}}/*** writer: amotama 勝手に借りてます、問題あったらごめんね*/public static long[] convolution(long[] a, long[] b) {int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;resultSize = Math.max(resultSize, 1);double[] aReal = new double[resultSize];double[] aImaginary = new double[resultSize];double[] bReal = new double[resultSize];double[] bImaginary = new double[resultSize];for (int i = 0; i < a.length; i++) aReal[i] = a[i];for (int i = 0; i < b.length; i++) bReal[i] = b[i];fft(aReal, aImaginary, false);if (a == b) {System.arraycopy(aReal, 0, bReal, 0, aReal.length);System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);} else {fft(bReal, bImaginary, false);}for (int i = 0; i < resultSize; i++) {double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];aReal[i] = real;}fft(aReal, aImaginary, true);long[] result = new long[a.length + b.length - 1];for (int i = 0; i < result.length; i++) result[i] = Math.round(aReal[i]);return result;}/*** writer: amotama 勝手に借りてます、問題あったらごめんね*/public static int[] convolution(int[] a, int[] b) {int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;resultSize = Math.max(resultSize, 1);double[] aReal = new double[resultSize];double[] aImaginary = new double[resultSize];double[] bReal = new double[resultSize];double[] bImaginary = new double[resultSize];for (int i = 0; i < a.length; i++) aReal[i] = a[i];for (int i = 0; i < b.length; i++) bReal[i] = b[i];fft(aReal, aImaginary, false);if (a == b) {System.arraycopy(aReal, 0, bReal, 0, aReal.length);System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);} else {fft(bReal, bImaginary, false);}for (int i = 0; i < resultSize; i++) {double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];aReal[i] = real;}fft(aReal, aImaginary, true);int[] result = new int[a.length + b.length - 1];for (int i = 0; i < result.length; i++) result[i] = (int) Math.round(aReal[i]);return result;}/*** Find a primitive root.** @param m A prime number.* @return Primitive root.*/private static int primitiveRoot(final 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;final int[] divs = new int[20];divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (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++) {boolean ok = true;for (int i = 0; i < cnt; i++) {if (MathLib.pow(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok) return g;}}/*** Ceil of power 2.** @param n Value.* @return Ceil of power 2.*/private static int ceilPow2(final int n) {int x = 0;while (1L << x < n) x++;return x;}/*** Garner's algorithm.** @param c Mod convolution results.* @param mods Mods.* @return Result.*/private static long garner(final long[] c, final int[] mods) {final int n = c.length + 1;final long[] cnst = new long[n];final long[] coef = new long[n];java.util.Arrays.fill(coef, 1);for (int i = 0; i < n - 1; i++) {final int m1 = mods[i];long v = (c[i] - cnst[i] + m1) % m1;v = v * MathLib.pow(coef[i], m1 - 2, m1) % m1;for (int j = i + 1; j < n; j++) {final long m2 = mods[j];cnst[j] = (cnst[j] + coef[j] * v) % m2;coef[j] = coef[j] * m1 % m2;}}return cnst[n - 1];}/*** Garner's algorithm.** @param c Mod convolution results.* @param mods Mods.* @return Result.*/private static int garner(int c0, int c1, int c2, final MathLib.Barrett[] mods) {final long[] cnst = new long[4];final long[] coef = new long[4];java.util.Arrays.fill(coef, 1);MathLib.Barrett m1 = mods[0];long v = m1.reduce(c0 - cnst[0] + m1.mod);v = m1.reduce(v * MathLib.pow(coef[0], m1.mod - 2, m1));{MathLib.Barrett m2 = mods[1];cnst[1] = m2.reduce(cnst[1] + coef[1] * v);coef[1] = m2.reduce(coef[1] * m1.mod);m2 = mods[2];cnst[2] = m2.reduce(cnst[2] + coef[2] * v);coef[2] = m2.reduce(coef[2] * m1.mod);m2 = mods[3];cnst[3] = m2.reduce(cnst[3] + coef[3] * v);coef[3] = m2.reduce(coef[3] * m1.mod);}m1 = mods[1];v = m1.reduce(c1 - cnst[1] + m1.mod);v = m1.reduce(v * MathLib.pow(coef[1], m1.mod - 2, m1));{MathLib.Barrett m2 = mods[2];cnst[2] = m2.reduce(cnst[2] + coef[2] * v);coef[2] = m2.reduce(coef[2] * m1.mod);m2 = mods[3];cnst[3] = m2.reduce(cnst[3] + coef[3] * v);coef[3] = m2.reduce(coef[3] * m1.mod);}m1 = mods[2];v = m1.reduce(c2 - cnst[2] + m1.mod);v = m1.reduce(v * MathLib.pow(coef[2], m1.mod - 2, m1));{MathLib.Barrett m2 = mods[3];cnst[3] = m2.reduce(cnst[3] + coef[3] * v);coef[3] = m2.reduce(coef[3] * m1.mod);}return (int) cnst[3];}/*** Garner's algorithm.** @param c Mod convolution results.* @param mods Mods.* @return Result.*/private static int garner1_000_000_007(int c0, int c1, int c2) {final long[] cnst = new long[4];final long[] coef = new long[4];java.util.Arrays.fill(coef, 1);long v = (c0 - cnst[0] + 754_974_721) % 754_974_721;v = v * MathLib.pow754_974_721(coef[0], 754_974_721 - 2) % 754_974_721;{cnst[1] = (cnst[1] + coef[1] * v) % 167_772_161;coef[1] = coef[1] * 754_974_721 % 167_772_161;cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;coef[2] = coef[2] * 754_974_721 % 469_762_049;cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;coef[3] = coef[3] * 754_974_721 % 1_000_000_007;}v = (c1 - cnst[1] + 167_772_161) % 167_772_161;v = v * MathLib.pow167_772_161(coef[1], 167_772_161 - 2) % 167_772_161;{cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;coef[2] = coef[2] * 167_772_161 % 469_762_049;cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;coef[3] = coef[3] * 167_772_161 % 1_000_000_007;}v = (c2 - cnst[2] + 469_762_049) % 469_762_049;v = v * MathLib.pow469_762_049(coef[2], 469_762_049 - 2) % 469_762_049;{cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;coef[3] = coef[3] * 469_762_049 % 1_000_000_007;}return (int) cnst[3];}/*** Pre-calculation for NTT.** @param mod NTT Prime.* @param g Primitive root of mod.* @return Pre-calculation table.*/private static long[] sumE(final int mod, final int g) {final long[] sum_e = new long[30];final long[] es = new long[30];final long[] ies = new long[30];final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);long e = MathLib.pow(g, mod - 1 >> cnt2, mod);long ie = MathLib.pow(e, mod - 2, mod);for (int i = cnt2; i >= 2; i--) {es[i - 2] = e;ies[i - 2] = ie;e = e * e % mod;ie = ie * ie % mod;}long now = 1;for (int i = 0; i < cnt2 - 2; i++) {sum_e[i] = es[i] * now % mod;now = now * ies[i] % mod;}return sum_e;}/*** Pre-calculation for inverse NTT.** @param mod Mod.* @param g Primitive root of mod.* @return Pre-calculation table.*/private static long[] sumIE(final int mod, final int g) {final long[] sum_ie = new long[30];final long[] es = new long[30];final long[] ies = new long[30];final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);long e = MathLib.pow(g, mod - 1 >> cnt2, mod);long ie = MathLib.pow(e, mod - 2, mod);for (int i = cnt2; i >= 2; i--) {es[i - 2] = e;ies[i - 2] = ie;e = e * e % mod;ie = ie * ie % mod;}long now = 1;for (int i = 0; i < cnt2 - 2; i++) {sum_ie[i] = ies[i] * now % mod;now = now * es[i] % mod;}return sum_ie;}/*** Inverse NTT.** @param a Target array.* @param sumIE Pre-calculation table.* @param mod NTT Prime.*/private static void butterflyInv(final long[] a, final long[] sumIE, final int mod) {final int n = a.length;final int h = ceilPow2(n);for (int ph = h; ph >= 1; ph--) {final int w = 1 << ph - 1, p = 1 << h - ph;long inow = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p];a[i + offset] = (l + r) % mod;a[i + offset + p] = (mod + l - r) * inow % mod;}final int x = Integer.numberOfTrailingZeros(~s);inow = inow * sumIE[x] % mod;}}}/*** Inverse NTT.** @param a Target array.* @param sumE Pre-calculation table.* @param mod NTT Prime.*/private static void butterfly(final long[] a, final long[] sumE, final int mod) {final int n = a.length;final int h = ceilPow2(n);for (int ph = 1; ph <= h; ph++) {final int w = 1 << ph - 1, p = 1 << h - ph;long now = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p] * now % mod;a[i + offset] = (l + r) % mod;a[i + offset + p] = (l - r + mod) % mod;}final int x = Integer.numberOfTrailingZeros(~s);now = now * sumE[x] % mod;}}}/*** Inverse NTT used mod 998_244_353.** @param a Target array.* @param sumIE Pre-calculation table.*/private static void butterflyInv998_244_353(final int[] a, final int[] sumIE) {final int n = a.length;final int h = ceilPow2(n);for (int ph = h; ph >= 1; ph--) {final int w = 1 << ph - 1, p = 1 << h - ph;long inow = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p];a[i + offset] = (int)((l + r) % 998_244_353);a[i + offset + p] = (int)((998_244_353 + l - r) * inow % 998_244_353);}final int x = Integer.numberOfTrailingZeros(~s);inow = inow * sumIE[x] % 998_244_353;}}}/*** Inverse NTT used mod 754_974_721.** @param a Target array.* @param sumIE Pre-calculation table.*/private static void butterflyInv754_974_721(final int[] a, final int[] sumIE) {final int n = a.length;final int h = ceilPow2(n);for (int ph = h; ph >= 1; ph--) {final int w = 1 << ph - 1, p = 1 << h - ph;long inow = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p];a[i + offset] = (int)((l + r) % 754_974_721);a[i + offset + p] = (int)((754_974_721 + l - r) * inow % 754_974_721);}final int x = Integer.numberOfTrailingZeros(~s);inow = inow * sumIE[x] % 754_974_721;}}}/*** Inverse NTT used mod 167_772_161.** @param a Target array.* @param sumIE Pre-calculation table.*/private static void butterflyInv167_772_161(final int[] a, final int[] sumIE) {final int n = a.length;final int h = ceilPow2(n);for (int ph = h; ph >= 1; ph--) {final int w = 1 << ph - 1, p = 1 << h - ph;long inow = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p];a[i + offset] = (int)((l + r) % 167_772_161);a[i + offset + p] = (int)((167_772_161 + l - r) * inow % 167_772_161);}final int x = Integer.numberOfTrailingZeros(~s);inow = inow * sumIE[x] % 167_772_161;}}}/*** Inverse NTT used mod 469_762_049.** @param a Target array.* @param sumIE Pre-calculation table.*/private static void butterflyInv469_762_049(final int[] a, final int[] sumIE) {final int n = a.length;final int h = ceilPow2(n);for (int ph = h; ph >= 1; ph--) {final int w = 1 << ph - 1, p = 1 << h - ph;long inow = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p];a[i + offset] = (int)((l + r) % 469_762_049);a[i + offset + p] = (int)((469_762_049 + l - r) * inow % 469_762_049);}final int x = Integer.numberOfTrailingZeros(~s);inow = inow * sumIE[x] % 469_762_049;}}}/*** Inverse NTT.** @param a Target array.* @param sumIE Pre-calculation table.* @param mod NTT Prime.*/private static void butterflyInv(final int[] a, final int[] sumIE, final MathLib.Barrett mod) {final int n = a.length;final int h = ceilPow2(n);for (int ph = h; ph >= 1; ph--) {final int w = 1 << ph - 1, p = 1 << h - ph;long inow = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p];long sum = l + r;if (sum >= mod.mod) sum -= mod.mod;a[i + offset] = (int)sum;a[i + offset + p] = mod.reduce((mod.mod + l - r) * inow);}final int x = Integer.numberOfTrailingZeros(~s);inow = mod.reduce(inow * sumIE[x]);}}}/*** Inverse NTT used mod 998_244_353.** @param a Target array.* @param sumE Pre-calculation table.* @param mod NTT Prime.*/private static void butterfly998_244_353(final int[] a, final int[] sumE) {final int n = a.length;final int h = ceilPow2(n);final long ADD = (long)(998_244_353 - 2) * 998_244_353;for (int ph = 1; ph <= h; ph++) {final int w = 1 << ph - 1, p = 1 << h - ph;long now = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p] * now;a[i + offset] = (int)((l + r) % 998_244_353);a[i + offset + p] = (int)((l - r + ADD) % 998_244_353);}final int x = Integer.numberOfTrailingZeros(~s);now = now * sumE[x] % 998_244_353;}}}/*** Inverse NTT used mod 754_974_721.** @param a Target array.* @param sumE Pre-calculation table.* @param mod NTT Prime.*/private static void butterfly754_974_721(final int[] a, final int[] sumE) {final int n = a.length;final int h = ceilPow2(n);final long ADD = (long)(754_974_721 - 2) * 754_974_721;for (int ph = 1; ph <= h; ph++) {final int w = 1 << ph - 1, p = 1 << h - ph;long now = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p] * now;a[i + offset] = (int)((l + r) % 754_974_721);a[i + offset + p] = (int)((l - r + ADD) % 754_974_721);}final int x = Integer.numberOfTrailingZeros(~s);now = now * sumE[x] % 754_974_721;}}}/*** Inverse NTT used mod 167_772_161.** @param a Target array.* @param sumE Pre-calculation table.* @param mod NTT Prime.*/private static void butterfly167_772_161(final int[] a, final int[] sumE) {final int n = a.length;final int h = ceilPow2(n);final long ADD = (long)(167_772_161 - 2) * 167_772_161;for (int ph = 1; ph <= h; ph++) {final int w = 1 << ph - 1, p = 1 << h - ph;long now = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p] * now;a[i + offset] = (int)((l + r) % 167_772_161);a[i + offset + p] = (int)((l - r + ADD) % 167_772_161);}final int x = Integer.numberOfTrailingZeros(~s);now = now * sumE[x] % 167_772_161;}}}/*** Inverse NTT used mod 469_762_049.** @param a Target array.* @param sumE Pre-calculation table.* @param mod NTT Prime.*/private static void butterfly469_762_049(final int[] a, final int[] sumE) {final int n = a.length;final int h = ceilPow2(n);final long ADD = (long)(469_762_049 - 2) * 469_762_049;for (int ph = 1; ph <= h; ph++) {final int w = 1 << ph - 1, p = 1 << h - ph;long now = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p] * now;a[i + offset] = (int)((l + r) % 469_762_049);a[i + offset + p] = (int)((l - r + ADD) % 469_762_049);}final int x = Integer.numberOfTrailingZeros(~s);now = now * sumE[x] % 469_762_049;}}}/*** Inverse NTT.** @param a Target array.* @param sumE Pre-calculation table.* @param mod NTT Prime.*/private static void butterfly(final int[] a, final int[] sumE, final MathLib.Barrett mod) {final int n = a.length;final int h = ceilPow2(n);final long ADD = (long)(mod.mod - 2) * mod.mod;for (int ph = 1; ph <= h; ph++) {final int w = 1 << ph - 1, p = 1 << h - ph;long now = 1;for (int s = 0; s < w; s++) {final int offset = s << h - ph + 1;for (int i = 0; i < p; i++) {final long l = a[i + offset];final long r = a[i + offset + p] * now;a[i + offset] = mod.reduce(l + r);a[i + offset + p] = mod.reduce(l - r + ADD);}final int x = Integer.numberOfTrailingZeros(~s);now = mod.reduce(now * sumE[x]);}}}/*** Convolution used mod 998_244_353.** @param a Target array 1.* @param b Target array 2.* @return Answer.*/public static int[] convolution998_244_353(int[] a, int[] b) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new int[0];final int z = 1 << ceilPow2(n + m - 1);{final int[] na = new int[z];final int[] nb = new int[z];System.arraycopy(a, 0, na, 0, n);System.arraycopy(b, 0, nb, 0, m);a = na;b = nb;}final int g = primitiveRoot(998_244_353);final int[] sume;{long[] s = sumE(998_244_353, g);sume = new int[s.length];for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];}final int[] sumie;{long[] s = sumIE(998_244_353, g);sumie = new int[s.length];for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];}butterfly998_244_353(a, sume);butterfly998_244_353(b, sume);for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 998_244_353);butterflyInv998_244_353(a, sumie);a = java.util.Arrays.copyOf(a, n + m - 1);final long iz = MathLib.pow998_244_353(z, 998_244_353 - 2);for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 998_244_353);return a;}/*** Convolution used mod 754_974_721.** @param a Target array 1.* @param b Target array 2.* @return Answer.*/public static int[] convolution754_974_721(int[] a, int[] b) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new int[0];final int z = 1 << ceilPow2(n + m - 1);{final int[] na = new int[z];final int[] nb = new int[z];System.arraycopy(a, 0, na, 0, n);System.arraycopy(b, 0, nb, 0, m);a = na;b = nb;}final int g = primitiveRoot(754_974_721);final int[] sume;{long[] s = sumE(754_974_721, g);sume = new int[s.length];for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];}final int[] sumie;{long[] s = sumIE(754_974_721, g);sumie = new int[s.length];for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];}butterfly754_974_721(a, sume);butterfly754_974_721(b, sume);for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 754_974_721);butterflyInv754_974_721(a, sumie);a = java.util.Arrays.copyOf(a, n + m - 1);final long iz = MathLib.pow754_974_721(z, 754_974_721 - 2);for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 754_974_721);return a;}/*** Convolution used mod 167_772_161.** @param a Target array 1.* @param b Target array 2.* @return Answer.*/public static int[] convolution167_772_161(int[] a, int[] b) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new int[0];final int z = 1 << ceilPow2(n + m - 1);{final int[] na = new int[z];final int[] nb = new int[z];System.arraycopy(a, 0, na, 0, n);System.arraycopy(b, 0, nb, 0, m);a = na;b = nb;}final int g = primitiveRoot(167_772_161);final int[] sume;{long[] s = sumE(167_772_161, g);sume = new int[s.length];for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];}final int[] sumie;{long[] s = sumIE(167_772_161, g);sumie = new int[s.length];for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];}butterfly167_772_161(a, sume);butterfly167_772_161(b, sume);for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 167_772_161);butterflyInv167_772_161(a, sumie);a = java.util.Arrays.copyOf(a, n + m - 1);final long iz = MathLib.pow167_772_161(z, 167_772_161 - 2);for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 167_772_161);return a;}/*** Convolution used mod 469_762_049.** @param a Target array 1.* @param b Target array 2.* @return Answer.*/public static int[] convolution469_762_049(int[] a, int[] b) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new int[0];final int z = 1 << ceilPow2(n + m - 1);{final int[] na = new int[z];final int[] nb = new int[z];System.arraycopy(a, 0, na, 0, n);System.arraycopy(b, 0, nb, 0, m);a = na;b = nb;}final int g = primitiveRoot(469_762_049);final int[] sume;{long[] s = sumE(469_762_049, g);sume = new int[s.length];for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];}final int[] sumie;{long[] s = sumIE(469_762_049, g);sumie = new int[s.length];for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];}butterfly469_762_049(a, sume);butterfly469_762_049(b, sume);for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 469_762_049);butterflyInv469_762_049(a, sumie);a = java.util.Arrays.copyOf(a, n + m - 1);final long iz = MathLib.pow469_762_049(z, 469_762_049 - 2);for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 469_762_049);return a;}/*** Convolution.** @param a Target array 1.* @param b Target array 2.* @param mod NTT Prime.* @return Answer.*/public static int[] convolution(int[] a, int[] b, final int mod) {MathLib.Barrett barrett = new MathLib.Barrett(mod);final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new int[0];final int z = 1 << ceilPow2(n + m - 1);{final int[] na = new int[z];final int[] nb = new int[z];System.arraycopy(a, 0, na, 0, n);System.arraycopy(b, 0, nb, 0, m);a = na;b = nb;}final int g = primitiveRoot(mod);final int[] sume;{long[] s = sumE(mod, g);sume = new int[s.length];for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];}final int[] sumie;{long[] s = sumIE(mod, g);sumie = new int[s.length];for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];}butterfly(a, sume, barrett);butterfly(b, sume, barrett);for (int i = 0; i < z; i++) a[i] = barrett.reduce((long) a[i] * b[i]);butterflyInv(a, sumie, barrett);a = java.util.Arrays.copyOf(a, n + m - 1);final long iz = MathLib.pow(z, mod - 2, mod);for (int i = 0; i < n + m - 1; i++) a[i] = barrett.reduce(a[i] * iz);return a;}/*** Convolution.** @param a Target array 1.* @param b Target array 2.* @param mod NTT Prime.* @return Answer.*/public static long[] convolution(long[] a, long[] b, final int mod) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new long[0];final int z = 1 << ceilPow2(n + m - 1);{final long[] na = new long[z];final long[] nb = new long[z];System.arraycopy(a, 0, na, 0, n);System.arraycopy(b, 0, nb, 0, m);a = na;b = nb;}final int g = primitiveRoot(mod);final long[] sume = sumE(mod, g);final long[] sumie = sumIE(mod, g);butterfly(a, sume, mod);butterfly(b, sume, mod);for (int i = 0; i < z; i++) {a[i] = a[i] * b[i] % mod;}butterflyInv(a, sumie, mod);a = java.util.Arrays.copyOf(a, n + m - 1);final long iz = MathLib.pow(z, mod - 2, mod);for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod;return a;}/*** Convolution.** @param a Target array 1.* @param b Target array 2.* @param mod Any mod.* @return Answer.*/public static long[] convolutionLL(final long[] a, final long[] b, final int mod) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new long[0];final int mod1 = 754_974_721;final int mod2 = 167_772_161;final int mod3 = 469_762_049;final long[] c1 = convolution(a, b, mod1);final long[] c2 = convolution(a, b, mod2);final long[] c3 = convolution(a, b, mod3);final int retSize = c1.length;final long[] ret = new long[retSize];final int[] mods = { mod1, mod2, mod3, mod };for (int i = 0; i < retSize; ++i) {ret[i] = garner(new long[] { c1[i], c2[i], c3[i] }, mods);}return ret;}/*** Convolution.** @param a Target array 1.* @param b Target array 2.* @param mod Any mod.* @return Answer.*/public static int[] convolutionLL(final int[] a, final int[] b, final int mod) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new int[0];final int mod1 = 754_974_721;final int mod2 = 167_772_161;final int mod3 = 469_762_049;final int[] c1 = convolution754_974_721(a, b);final int[] c2 = convolution167_772_161(a, b);final int[] c3 = convolution469_762_049(a, b);final int retSize = c1.length;final int[] ret = new int[retSize];final MathLib.Barrett[] mods = { new MathLib.Barrett(mod1), new MathLib.Barrett(mod2),new MathLib.Barrett(mod3), new MathLib.Barrett(mod) };for (int i = 0; i < retSize; ++i) ret[i] = garner(c1[i], c2[i], c3[i], mods);return ret;}/*** Convolution used mod 1_000_000_007.** @param a Target array 1.* @param b Target array 2.* @return Answer.*/public static int[] convolution1_000_000_007(final int[] a, final int[] b) {final int n = a.length;final int m = b.length;if (n == 0 || m == 0) return new int[0];final int[] c1 = convolution754_974_721(a, b);final int[] c2 = convolution167_772_161(a, b);final int[] c3 = convolution469_762_049(a, b);final int retSize = c1.length;final int[] ret = new int[retSize];for (int i = 0; i < retSize; ++i) ret[i] = garner1_000_000_007(c1[i], c2[i], c3[i]);return ret;}/*** Convolution. need: length < 2000** @param a Target array 1.* @param b Target array 2.* @param mod Any mod.* @return Answer.*/public static int[] convolutionLL2(final int[] a, final int[] b, final int mod) {if (Math.max(a.length, b.length) < 4000) {long[] la = new long[a.length], ha = new long[a.length], ma = new long[a.length], lb = new long[b.length],hb = new long[b.length], mb = new long[b.length];MathLib.Barrett barrett = new MathLib.Barrett(mod);for (int i = 0; i < a.length; ++i) {ha[i] = a[i] >> 15;la[i] = a[i] & 0x7FFF;ma[i] = la[i] + ha[i];}for (int i = 0; i < b.length; ++i) {hb[i] = b[i] >> 15;lb[i] = b[i] & 0x7FFF;mb[i] = lb[i] + hb[i];}long[] l = convolution(la, lb), h = convolution(ha, hb), m = convolution(ma, mb);int[] ret = new int[m.length];for (int i = 0; i < m.length; ++i) {h[i] = barrett.reduce(h[i]);m[i] = barrett.reduce(m[i] - l[i] - h[i] + (long)m.length * mod);ret[i] = barrett.reduce((h[i] << 30) + (m[i] << 15) + l[i]);}return ret;}return convolutionLL(a, b, mod);}/*** Naive convolution. (Complexity is O(N^2)!!)** @param a Target array 1.* @param b Target array 2.* @param mod Mod.* @return Answer.*/public static long[] convolutionNaive(final long[] a, final long[] b, final int mod) {final int n = a.length;final int m = b.length;final int k = n + m - 1;final long[] ret = new long[k];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret[i + j] += a[i] * b[j] % mod;ret[i + j] %= mod;}}return ret;}}}class FastScanner {private final java.io.InputStream in = System.in;private final byte[] buffer = new byte[8192];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) return true;ptr = 0;try {buflen = in.read(buffer);} catch (java.io.IOException e) {e.printStackTrace();}return buflen > 0;}private byte readByte() {return hasNextByte() ? buffer[ptr++] : -1;}private static boolean isPrintableChar(byte c) {return 32 < c || c < 0;}private static boolean isNumber(int c) {return '0' <= c && c <= '9';}public boolean hasNext() {while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;return hasNextByte();}public String next() {if (!hasNext()) throw new java.util.NoSuchElementException();StringBuilder sb = new StringBuilder();byte b;while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);return sb.toString();}public final char nextChar() {if (!hasNext()) throw new java.util.NoSuchElementException();return (char) readByte();}public final long nextLong() {if (!hasNext()) throw new java.util.NoSuchElementException();long n = 0;try {byte b = readByte();if (b == '-') {while (isNumber(b = readByte())) n = n * 10 + '0' - b;return n;} else if (!isNumber(b)) throw new NumberFormatException();do n = n * 10 + b - '0'; while (isNumber(b = readByte()));} catch (java.util.NoSuchElementException e) {}return n;}public final int nextInt() {if (!hasNext()) throw new java.util.NoSuchElementException();int n = 0;try {byte b = readByte();if (b == '-') {while (isNumber(b = readByte())) n = n * 10 + '0' - b;return n;} else if (!isNumber(b)) throw new NumberFormatException();do n = n * 10 + b - '0'; while (isNumber(b = readByte()));} catch (java.util.NoSuchElementException e) {}return n;}public double nextDouble() {return Double.parseDouble(next());}}class Arrays {public static void sort(final int[] array) {sort(array, 0, array.length);}public static void sort(final int[] array, int fromIndex, int toIndex) {if (toIndex - fromIndex <= 512) {java.util.Arrays.sort(array, fromIndex, toIndex);return;}sort(array, fromIndex, toIndex, 0, new int[array.length]);}private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) {if (to - from <= 512) {java.util.Arrays.sort(a, from, to);return;}final int BUCKET_SIZE = 256;final int INT_RECURSION = 4;final int MASK = 0xff;final int shift = l << 3;final int[] cnt = new int[BUCKET_SIZE + 1];final int[] put = new int[BUCKET_SIZE];for (int i = from; i < to; i++) ++cnt[(a[i] >>> shift & MASK) + 1];for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];for (int i = from; i < to; i++) {int bi = a[i] >>> shift & MASK;bucket[cnt[bi] + put[bi]++] = a[i];}for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {int begin = cnt[i];int len = cnt[i + 1] - begin;System.arraycopy(bucket, begin, a, idx, len);idx += len;}final int nxtL = l + 1;if (nxtL < INT_RECURSION) {sort(a, from, to, nxtL, bucket);if (l == 0) {int lft, rgt;lft = from - 1;rgt = to;while (rgt - lft > 1) {int mid = lft + rgt >> 1;if (a[mid] < 0) lft = mid;else rgt = mid;}reverse(a, from, rgt);reverse(a, rgt, to);}}}public static void sort(final long[] array) {sort(array, 0, array.length);}public static void sort(final long[] array, int fromIndex, int toIndex) {if (toIndex - fromIndex <= 512) {java.util.Arrays.sort(array, fromIndex, toIndex);return;}sort(array, fromIndex, toIndex, 0, new long[array.length]);}private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) {final int BUCKET_SIZE = 256;final int LONG_RECURSION = 8;final int MASK = 0xff;final int shift = l << 3;final int[] cnt = new int[BUCKET_SIZE + 1];final int[] put = new int[BUCKET_SIZE];for (int i = from; i < to; i++) ++cnt[(int) ((a[i] >>> shift & MASK) + 1)];for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];for (int i = from; i < to; i++) {int bi = (int) (a[i] >>> shift & MASK);bucket[cnt[bi] + put[bi]++] = a[i];}for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {int begin = cnt[i];int len = cnt[i + 1] - begin;System.arraycopy(bucket, begin, a, idx, len);idx += len;}final int nxtL = l + 1;if (nxtL < LONG_RECURSION) {sort(a, from, to, nxtL, bucket);if (l == 0) {int lft, rgt;lft = from - 1;rgt = to;while (rgt - lft > 1) {int mid = lft + rgt >> 1;if (a[mid] < 0) lft = mid;else rgt = mid;}reverse(a, from, rgt);reverse(a, rgt, to);}}}public static void reverse(int[] array) {reverse(array, 0, array.length);}public static void reverse(int[] array, int fromIndex, int toIndex) {for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {int swap = array[fromIndex];array[fromIndex] = array[toIndex];array[toIndex] = swap;}}public static void reverse(long[] array) {reverse(array, 0, array.length);}public static void reverse(long[] array, int fromIndex, int toIndex) {for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {long swap = array[fromIndex];array[fromIndex] = array[toIndex];array[toIndex] = swap;}}public static void shuffle(int[] array) {java.util.Random rnd = new java.util.Random();for (int i = 0; i < array.length; ++i) {int j = rnd.nextInt(array.length - i) + i;int swap = array[i];array[i] = array[j];array[j] = swap;}}public static void shuffle(long[] array) {java.util.Random rnd = new java.util.Random();for (int i = 0; i < array.length; ++i) {int j = rnd.nextInt(array.length - i) + i;long swap = array[i];array[i] = array[j];array[j] = swap;}}}class IntMath {public static int gcd(int a, int b) {while (a != 0) if ((b %= a) != 0) a %= b;else return a;return b;}public static int gcd(int... array) {int ret = array[0];for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);return ret;}public static long gcd(long a, long b) {while (a != 0) if ((b %= a) != 0) a %= b;else return a;return b;}public static long gcd(long... array) {long ret = array[0];for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);return ret;}public static long lcm(long a, long b) {return a / gcd(a, b) * b;}public static int pow(int a, int b) {int ans = 1;for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;return ans;}public static long pow(long a, long b) {long ans = 1;for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;return ans;}public static int pow(int a, long b, int mod) {if (b < 0) b = b % (mod - 1) + mod - 1;long ans = 1;for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod;return (int) ans;}public static int pow(long a, long b, int mod) {return pow((int) (a % mod), b, mod);}public static int floorsqrt(long n) {return (int) Math.sqrt(n + 0.1);}public static int ceilsqrt(long n) {return n <= 1 ? (int) n : (int) Math.sqrt(n - 0.1) + 1;}}