Submit Info #24111

Problem Lang User Status Time Memory
Bernoulli Number java suisen AC 1010 ms 100.54 MiB

ケース詳細
Name Status Time Memory
0_00 AC 61 ms 9.98 MiB
100000_00 AC 415 ms 57.21 MiB
10000_00 AC 189 ms 17.27 MiB
1000_00 AC 94 ms 10.87 MiB
100_00 AC 64 ms 10.10 MiB
1_00 AC 66 ms 10.04 MiB
200000_00 AC 630 ms 86.52 MiB
300000_00 AC 1000 ms 100.54 MiB
400000_00 AC 991 ms 100.31 MiB
500000_00 AC 1010 ms 97.17 MiB
example_00 AC 63 ms 9.99 MiB

import java.io.InputStream; import java.util.Arrays; import java.util.Objects; import java.util.PrimitiveIterator; import java.util.function.IntBinaryOperator; import java.util.function.IntFunction; import java.util.function.IntPredicate; import java.util.function.IntUnaryOperator; import java.util.function.LongBinaryOperator; import java.util.function.LongPredicate; import java.util.function.LongUnaryOperator; public class Main { public static void main(String[] args) throws Exception { ExtendedScanner sc = new ExtendedScanner(); FastPrintStream pw = new FastPrintStream(); solve(sc, pw); sc.close(); pw.flush(); pw.close(); } public static void solve(ExtendedScanner sc, FastPrintStream pw) { ModPolynomialFactory mpf = ModPolynomialFactory.ofNTTPrime((int) Const.MOD998244353); int n = sc.nextInt(); long[] st = Combinatrics.bernoulli(n, mpf); for (long e : st) { pw.print(e).print(' '); } pw.println(); } } /** * @author https://atcoder.jp/users/suisen * * 1. DESTRUCTIVE methods for long arrays. * 2. methods that receives arrays and return some results (except for long arrays). */ final class LongArrays { private LongArrays(){} public static void swap(final long[] a, final int u, final int v) { final long tmp = a[u]; a[u] = a[v]; a[v] = tmp; } public static void reverse(final long[] a, int begin, int end) { while (end - begin > 1) swap(a, begin++, --end); } public static void reverse(final long[] a) {reverse(a, 0, a.length);} public static void sortDescending(final long[] a) {Arrays.sort(a); reverse(a);} public static long fold(final long[] a, final LongBinaryOperator op) { long ret = a[0]; for (int i = 1; i < a.length; i++) ret = op.applyAsLong(ret, a[i]); return ret; } public static long sum(final long[] a) {return fold(a, Long::sum);} public static long max(final long[] a) {return fold(a, Long::max);} public static long min(final long[] a) {return fold(a, Long::min);} public static IntLongPair maxWithIndex(final long[] a) { long max = max(a); return new IntLongPair(find(a, max), max); } public static IntLongPair minWithIndex(final long[] a) { long min = min(a); return new IntLongPair(find(a, min), min); } public static int find(final long[] a, final long v) { for (int i = 0; i < a.length; i++) if (a[i] == v) return i; return -1; } public static void map(final long[] a, final LongUnaryOperator op) {Arrays.setAll(a, i -> op.applyAsLong(a[i]));} public static int filter(final long[] src, final long[] dst, final LongPredicate p) { int idx = 0; for (final long e : src) if (p.test(e)) dst[idx++] = e; return idx; } public static int filterIndex(final long[] dst, final int beginIndex, final int endIndex, final LongPredicate p) { int idx = 0; for (int i = beginIndex; i < endIndex; i++) if (p.test(i)) dst[idx++] = i; return idx; } public static int filterIndex(final long dst[], final int endIndex, final LongPredicate p) { return filterIndex(dst, 0, endIndex, p); } public static void accumulate(final long[] a, final LongBinaryOperator op) { for (int i = 1; i < a.length; i++) a[i] = op.applyAsLong(a[i - 1], a[i]); } public static void accumulate(final long[] a) { for (int i = 1; i < a.length; i++) a[i] += a[i - 1]; } public static void permute(long[] a, int[] p) { int n = p.length; boolean[] settled = new boolean[n]; for (int i = 0; i < n; i++) { for (int j = i; !settled[j]; j = p[j]) { if (p[j] == i) { settled[j] = true; break; } swap(a, j, p[j]); settled[j] = true; } } } public static int lowerBound(long[] sorted, long key) { int n = sorted.length; int l = -1, r = n; while (r - l > 1) { int m = (l + r) >> 1; if (sorted[m] < key) l = m; else r = m; } return r; } public static int upperBound(long[] sorted, long key) { int n = sorted.length; int l = -1, r = n; while (r - l > 1) { int m = (l + r) >> 1; if (sorted[m] <= key) l = m; else r = m; } return r; } public static int countRange(long[] sorted, long fromKey, long toKey) { return lowerBound(sorted, toKey) - lowerBound(sorted, fromKey); } public static int compare(final long[] a, final long[] b) { for (int i = 0; i < a.length; i++) { if (i >= b.length) return -1; if (a[i] > b[i]) return 1; if (a[i] < b[i]) return -1; } return a.length < b.length ? 1 : 0; } public static boolean equals(final long[] a, final long[] b) {return compare(a, b) == 0;} public static String join(final long[] a, final String sep) { final StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { sb.append(a[i]); if (i < a.length - 1) sb.append(sep); } return sb.toString(); } public static String joinWithPrefixAndSuffix(final long[] a, final IntFunction<String> idxToPre, final IntFunction<String> idxToSuf, final String sep) { final StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { sb.append(idxToPre.apply(i)).append(a[i]).append(idxToSuf.apply(i)); if (i < a.length - 1) sb.append(sep); } return sb.toString(); } } /** * @author https://atcoder.jp/users/suisen */ final class ExtendedScanner extends FastScanner { public ExtendedScanner() {super();} public ExtendedScanner(InputStream in) {super(in);} public int[] ints(final int n) { final int[] a = new int[n]; Arrays.setAll(a, $ -> nextInt()); return a; } public int[] ints(final int n, final IntUnaryOperator f) { final int[] a = new int[n]; Arrays.setAll(a, $ -> f.applyAsInt(nextInt())); return a; } public int[][] ints(final int n, final int m) { final int[][] a = new int[n][]; Arrays.setAll(a, $ -> ints(m)); return a; } public int[][] ints(final int n, final int m, final IntUnaryOperator f) { final int[][] a = new int[n][]; Arrays.setAll(a, $ -> ints(m, f)); return a; } public long[] longs(final int n) { final long[] a = new long[n]; Arrays.setAll(a, $ -> nextLong()); return a; } public long[] longs(final int n, final LongUnaryOperator f) { final long[] a = new long[n]; Arrays.setAll(a, $ -> f.applyAsLong(nextLong())); return a; } public long[][] longs(final int n, final int m) { final long[][] a = new long[n][]; Arrays.setAll(a, $ -> longs(m)); return a; } public long[][] longs(final int n, final int m, final LongUnaryOperator f) { final long[][] a = new long[n][]; Arrays.setAll(a, $ -> longs(m, f)); return a; } public char[][] charArrays(final int n) { final char[][] c = new char[n][]; Arrays.setAll(c, $ -> nextChars()); return c; } public char[][] charArrays(final int n, final int m) { final char[][] c = new char[n][]; Arrays.setAll(c, $ -> nextChars(m)); return c; } public double[] doubles(final int n) { final double[] a = new double[n]; Arrays.setAll(a, $ -> nextDouble()); return a; } public double[][] doubles(final int n, final int m) { final double[][] a = new double[n][]; Arrays.setAll(a, $ -> doubles(m)); return a; } public String[] strings(final int n) { final String[] s = new String[n]; Arrays.setAll(s, $ -> next()); return s; } public String[] strings(final int n, final int m) { final String[] s = new String[n]; Arrays.setAll(s, $ -> next(m)); return s; } } /** * @author https://atcoder.jp/users/suisen */ final class IntArrayList implements Iterable<Integer> { private int[] a; private int tail = 0; private static final int DEFAULT_SIZE = 64; public IntArrayList(final int capacity) {this.a = new int[Math.max(1, capacity)];} public IntArrayList() {this(DEFAULT_SIZE);} public void add(final int v) { if (tail == a.length) grow(); a[tail++] = v; } public int removeLast() {return a[--tail];} public int get(final int i) { if (i >= tail) throw new IndexOutOfBoundsException("Index " + i + " out of bounds for length " + size()); return a[i]; } public void set(final int i, final int v) { if (i >= tail) throw new IndexOutOfBoundsException("Index " + i + " out of bounds for length " + size()); a[i] = v; } private void grow() { final int[] b = new int[a.length << 1]; System.arraycopy(a, 0, b, 0, a.length); a = b; } public int size() {return tail;} public void clear() {tail = 0;} public void reverse(final int begin, final int end) {IntArrays.reverse(a, begin, end);} public void reverse() {IntArrays.reverse(a, 0, tail);} public int[] toArray() { final int[] ret = new int[tail]; System.arraycopy(a, 0, ret, 0, tail); return ret; } public void sort() {Arrays.sort(a, 0, tail);} public boolean addIf(final int v, final IntPredicate p) { if (p.test(v)) {add(v); return true;} return false; } public PrimitiveIterator.OfInt iterator() {return new IntArrayListIterator();} private class IntArrayListIterator implements PrimitiveIterator.OfInt { private int i = 0; public boolean hasNext() {return i < tail;} public int nextInt() {return a[i++];} } } class ModPolynomialFactory { public final long MOD; public final Convolution cnv; public final ModArithmetic ma; private ModPolynomialFactory(int mod, boolean isNTTPrime) { this.MOD = mod; this.cnv = isNTTPrime ? Convolution.ofNTTPrime(mod) : Convolution.of(mod); this.ma = ModArithmetic.of(mod); } public static ModPolynomialFactory of(int mod) { return new ModPolynomialFactory(mod, false); } public static ModPolynomialFactory ofNTTPrime(int mod) { return new ModPolynomialFactory(mod, true); } public ModPolynomial create(long[] c, int n) { return new ModPolynomial(c, n); } public ModPolynomial create(long[] c) { return new ModPolynomial(c); } public ModPolynomial cut(ModPolynomial f, int maxDegInclusive) { long[] c = new long[maxDegInclusive + 1]; System.arraycopy(f.C, 0, c, 0, Math.min(f.N, maxDegInclusive + 1)); return new ModPolynomial(c); } public ModPolynomial add(ModPolynomial f, ModPolynomial g) { long[] hc = new long[Math.max(f.N, g.N)]; System.arraycopy(f.C, 0, hc, 0, f.N); for (int i = 0; i < g.N; i++) { hc[i] = hc[i] + g.C[i]; } return new ModPolynomial(hc); } public ModPolynomial sub(ModPolynomial f, ModPolynomial g) { long[] hc = new long[Math.max(f.N, g.N)]; System.arraycopy(f.C, 0, hc, 0, f.N); for (int i = 0; i < g.N; i++) { hc[i] = hc[i] - g.C[i]; } return new ModPolynomial(hc); } public ModPolynomial mul(ModPolynomial f, long a) { a = ma.mod(a); long[] c = new long[f.N]; for (int i = 0; i < f.N; i++) c[i] = ma.mul(a, f.C[i]); return new ModPolynomial(c); } public ModPolynomial mul(ModPolynomial f, ModPolynomial g) { return new ModPolynomial(cnv.convolution(f.C, g.C)); } public ModPolynomial mul(ModPolynomial f, ModPolynomial g, int maxDegInclusive) { return new ModPolynomial(cnv.convolution(f.C, g.C), maxDegInclusive); } public ModPolynomial div(ModPolynomial f, ModPolynomial g, int maxDegInclusive) { return mul(f, inv(g, maxDegInclusive), maxDegInclusive); } public ModPolynomial inv(ModPolynomial f, int maxDegInclusive) { int k = 1; ModPolynomial inv = new ModPolynomial(new long[]{ma.inv(f.C[0])}); while (k < maxDegInclusive + 1) { k <<= 1; inv = inv.mul(2).sub(inv.mul(inv, k).mul(cut(f, k), k)); } return cut(inv, maxDegInclusive); } public ModPolynomial differentiate(ModPolynomial f) { long[] c = new long[f.N - 1]; for (int i = 1; i < f.N; i++) c[i - 1] = ma.mul(f.C[i], i); return new ModPolynomial(c); } public ModPolynomial integrate(ModPolynomial f) { long[] c = new long[f.N + 1]; long[] invs = ma.rangeInv(f.N + 1); for (int i = 1; i <= f.N; i++) c[i] = ma.mul(f.C[i - 1], invs[i]); return new ModPolynomial(c); } public ModPolynomial log(ModPolynomial f, int maxDegInclusive) { return integrate(mul(differentiate(f), inv(f, maxDegInclusive), maxDegInclusive - 1)); } public ModPolynomial exp(ModPolynomial f, int maxDegInclusive) { ModPolynomial g = new ModPolynomial(new long[]{1}); int k = 1; while (k < maxDegInclusive + 1) { k <<= 1; ModPolynomial tmp = sub(cut(f, k), log(g, k)); tmp.C[0] = ma.add(tmp.C[0], 1); g = mul(g, tmp, k); } return cut(g, maxDegInclusive); } public ModPolynomial pow(ModPolynomial f, long k, int maxDegInclusive) { int t0 = 0; while (t0 < f.N && f.C[t0] == 0) t0++; if ((long) t0 * k >= f.N) return new ModPolynomial(new long[]{0}); ModPolynomial g = new ModPolynomial(java.util.Arrays.copyOfRange(f.C, t0, f.N)); long base = g.C[0]; g = g.mul(ma.inv(base)); ModPolynomial h = exp(log(g, maxDegInclusive).mul(k), maxDegInclusive).mul(ma.pow(base, k)); long[] c = new long[maxDegInclusive + 1]; System.arraycopy(h.C, 0, c, (int) (t0 * k), (int) (maxDegInclusive + 1 - t0 * k)); return new ModPolynomial(c); } public ModPolynomial sqrt(ModPolynomial f, int maxDegInclusive) { int i = 0; while (i < f.N && f.C[i] == 0) i++; if (i == f.N) return new ModPolynomial(new long[]{0}); if ((i & 1) == 1) return null; java.util.OptionalLong ops = ma.sqrt(f.C[i]); if (ops.isEmpty()) return null; long s = ops.getAsLong(); ModPolynomial g = new ModPolynomial(java.util.Arrays.copyOfRange(f.C, i, f.N)); g = mul(exp(mul(log(mul(g, ma.inv(g.C[0])), maxDegInclusive), ma.inv(2)), maxDegInclusive), s); long[] sqrt = new long[i / 2 + g.N]; System.arraycopy(g.C, 0, sqrt, i / 2, g.N); return new ModPolynomial(sqrt, maxDegInclusive); } // public static long[] lagrangePolynomial(long[] x, long[] y, NTT ntt) { // long mod = ntt.MOD; // int m = x.length; // int n = 1; while (n < m) n <<= 1; // long[][] seg = new long[n << 1][]; // for (int k = 0; k < m; k++) { // seg[n + k] = new long[]{-x[k], 1}; // } // for (int k = m; k < n; k++) { // seg[n + k] = new long[]{1}; // } // for (int k = n - 1; k > 0; k--) { // seg[k] = ntt.convolution(seg[k << 1 | 0], seg[k << 1 | 1]); // } // long[] l = seg[1]; // seg = null; // int d = l.length - 1; // for (int i = 0; i < d; i++) { // l[i] = (l[i + 1] * (i + 1)) % mod; // } // l[d] = 0; // } public class ModPolynomial { final int N; final long[] C; ModPolynomial(long[] c, int n) { this.N = n + 1; this.C = new long[N]; int l = Math.min(N, c.length); for (int i = 0; i < l; i++) { C[i] = ma.mod(c[i]); } } ModPolynomial(long[] c) { int n = c.length - 1; while (n > 0 && c[n] == 0) n--; this.N = n + 1; this.C = new long[N]; for (int i = 0; i < N; i++) C[i] = ma.mod(c[i]); } public long apply(long x) { long ret = C[N - 1]; for (int i = N - 2; i >= 0; i--) ret = ma.mod(ret * x + C[i]); return ret; } public ModPolynomial add(ModPolynomial f) {return ModPolynomialFactory.this.add(this, f);} public ModPolynomial sub(ModPolynomial f) {return ModPolynomialFactory.this.sub(this, f);} public ModPolynomial mul(ModPolynomial f) {return ModPolynomialFactory.this.mul(this, f);} public ModPolynomial mul(ModPolynomial f, int maxDegInclusive) { return ModPolynomialFactory.this.mul(this, f, maxDegInclusive); } public ModPolynomial mul(long a) {return ModPolynomialFactory.this.mul(this, a);} public ModPolynomial div(ModPolynomial f, int maxDegInclusive) { return ModPolynomialFactory.this.div(this, f, maxDegInclusive); } public ModPolynomial inv(int maxDegInclusive) { return ModPolynomialFactory.this.inv(this, maxDegInclusive); } public ModPolynomial differentiate() {return ModPolynomialFactory.this.differentiate(this);} public ModPolynomial integrate () {return ModPolynomialFactory.this.integrate(this);} public ModPolynomial log(int maxDegInclusive) {return ModPolynomialFactory.this.log(this, maxDegInclusive);} public ModPolynomial exp(int maxDegInclusive) {return ModPolynomialFactory.this.exp(this, maxDegInclusive);} public ModPolynomial pow(long n, int maxDegInclusive) { return ModPolynomialFactory.this.pow(this, n, maxDegInclusive); } public ModPolynomial sqrt(int maxDegInclusive) { return ModPolynomialFactory.this.sqrt(this, maxDegInclusive); } public long getCoef(int deg) {return C[deg];} public long[] getCoefs() {return C;} } } /** * @author https://atcoder.jp/users/suisen */ class FastPrintStream implements AutoCloseable { private static final int BUF_SIZE = 1 << 15; private final byte[] buf = new byte[BUF_SIZE]; private int ptr = 0; private final java.lang.reflect.Field strField; private final java.nio.charset.CharsetEncoder encoder; private java.io.OutputStream out; public FastPrintStream(java.io.OutputStream out) { this.out = out; java.lang.reflect.Field f; try { f = java.lang.String.class.getDeclaredField("value"); f.setAccessible(true); } catch (NoSuchFieldException | SecurityException e) { f = null; } this.strField = f; this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder(); } public FastPrintStream(java.io.File file) throws java.io.IOException { this(new java.io.FileOutputStream(file)); } public FastPrintStream(java.lang.String filename) throws java.io.IOException { this(new java.io.File(filename)); } public FastPrintStream() { this(System.out); try { java.lang.reflect.Field f = java.io.PrintStream.class.getDeclaredField("autoFlush"); f.setAccessible(true); f.set(System.out, false); } catch (IllegalAccessException | IllegalArgumentException | NoSuchFieldException e) { // ignore } } public FastPrintStream println() { if (ptr == BUF_SIZE) internalFlush(); buf[ptr++] = (byte) '\n'; return this; } public FastPrintStream println(java.lang.Object o) { return print(o).println(); } public FastPrintStream println(java.lang.String s) { return print(s).println(); } public FastPrintStream println(char[] s) { return print(s).println(); } public FastPrintStream println(char c) { return print(c).println(); } public FastPrintStream println(int x) { return print(x).println(); } public FastPrintStream println(long x) { return print(x).println(); } public FastPrintStream println(double d, int precision) { return print(d, precision).println(); } private FastPrintStream print(byte[] bytes) { int n = bytes.length; if (ptr + n > BUF_SIZE) { internalFlush(); try { out.write(bytes); } catch (java.io.IOException e) { throw new RuntimeException(); } } else { System.arraycopy(bytes, 0, buf, ptr, n); ptr += n; } return this; } public FastPrintStream print(java.lang.Object o) { return print(o.toString()); } public FastPrintStream print(java.lang.String s) { if (strField == null) { return print(s.getBytes()); } else { try { Object value = strField.get(s); if (value instanceof byte[]) { return print((byte[]) value); } else { return print((char[]) value); } } catch (IllegalAccessException e) { return print(s.getBytes()); } } } public FastPrintStream print(char[] s) { try { return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array()); } catch (java.nio.charset.CharacterCodingException e) { byte[] bytes = new byte[s.length]; for (int i = 0; i < s.length; i++) { bytes[i] = (byte) s[i]; } return print(bytes); } } public FastPrintStream print(char c) { if (ptr == BUF_SIZE) internalFlush(); buf[ptr++] = (byte) c; return this; } public FastPrintStream print(int x) { if (x == 0) { if (ptr == BUF_SIZE) internalFlush(); buf[ptr++] = '0'; return this; } int d = len(x); if (ptr + d > BUF_SIZE) internalFlush(); if (x < 0) { buf[ptr++] = '-'; x = -x; d--; } int j = ptr += d; while (x > 0) { buf[--j] = (byte) ('0' + (x % 10)); x /= 10; } return this; } public FastPrintStream print(long x) { if (x == 0) { if (ptr == BUF_SIZE) internalFlush(); buf[ptr++] = '0'; return this; } int d = len(x); if (ptr + d > BUF_SIZE) internalFlush(); if (x < 0) { buf[ptr++] = '-'; x = -x; d--; } int j = ptr += d; while (x > 0) { buf[--j] = (byte) ('0' + (x % 10)); x /= 10; } return this; } public FastPrintStream print(double d, int precision) { if (d < 0) { print('-'); d = -d; } d += Math.pow(10, -precision) / 2; print((long) d).print('.'); d -= (long) d; for(int i = 0; i < precision; i++){ d *= 10; print((int) d); d -= (int) d; } return this; } private void internalFlush() { try { out.write(buf, 0, ptr); ptr = 0; } catch (java.io.IOException e) { throw new RuntimeException(e); } } public void flush() { try { out.write(buf, 0, ptr); out.flush(); ptr = 0; } catch (java.io.IOException e) { throw new RuntimeException(e); } } public void close() { try { out.close(); } catch (java.io.IOException e) { throw new RuntimeException(e); } } private static int len(int x) { int d = 1; if (x >= 0) {d = 0; x = -x;} int p = -10; for (int i = 1; i < 10; i++, p *= 10) if (x > p) return i + d; return 10 + d; } private static int len(long x) { int d = 1; if (x >= 0) {d = 0; x = -x;} long p = -10; for (int i = 1; i < 19; i++, p *= 10) if (x > p) return i + d; return 19 + d; } } /** * @author https://atcoder.jp/users/suisen */ final class LongArrayList implements Iterable<Long> { private long[] a; private int tail = 0; private static final int DEFAULT_SIZE = 64; public LongArrayList(final int capacity) {this.a = new long[Math.max(1, capacity)];} public LongArrayList() {this(DEFAULT_SIZE);} public void add(final long v) { if (tail == a.length) grow(); a[tail++] = v; } public long removeLast() {return a[--tail];} public long get(final int i) { if (i >= a.length) throw new IndexOutOfBoundsException("Index " + i + " out of bounds for length " + size()); return a[i]; } public void set(final int i, final long v) { if (i >= a.length) throw new IndexOutOfBoundsException("Index " + i + " out of bounds for length " + size()); a[i] = v; } private void grow() { final long[] b = new long[a.length << 1]; System.arraycopy(a, 0, b, 0, a.length); a = b; } public int size() {return tail;} public void clear() {tail = 0;} public void reverse(final int begin, final int end) {LongArrays.reverse(a, begin, end);} public void reverse() {LongArrays.reverse(a, 0, tail);} public long[] toArray() { final long[] ret = new long[tail]; System.arraycopy(a, 0, ret, 0, tail); return ret; } public void sort() {Arrays.sort(a, 0, tail);} public boolean addIf(final long v, final LongPredicate p) { if (p.test(v)) {add(v); return true;} return false; } public PrimitiveIterator.OfLong iterator() {return new LongArrayListIterator();} private class LongArrayListIterator implements PrimitiveIterator.OfLong { private int i = 0; public boolean hasNext() {return i < tail;} public long nextLong() {return a[i++];} } } class Combinatrics { /** * @return (x - l) * (x - (l + 1)) * ... (x * (r - 1)) */ public static ModPolynomialFactory.ModPolynomial perm(ModPolynomialFactory mpf, int l, int r) { if (r - l == 1) { return mpf.create(new long[]{-l, 1}, 1); } else if (r - l == 2) { return mpf.create(new long[]{(long) l * (l + 1), - (2 * l + 1), 1}, 2); } int m = (l + r) >> 1; return mpf.mul(perm(mpf, l, m), perm(mpf, m, r)); } public static long[] stirling1(int n, ModPolynomialFactory mpf) { if (n == 0) { return new long[]{1}; } else if (n == 1) { return new long[]{0, 1}; } return perm(mpf, 0, n).getCoefs(); } public static long[] stirling2(int n, ModPolynomialFactory mpf) { if (n == 0) { return new long[]{1}; } int[] div = MathUtil.osak(n); long[] pow = new long[n + 1]; pow[0] = 0; pow[1] = 1; for (int i = 2; i <= n; i++) { pow[i] = div[i] == i ? mpf.ma.pow(i, n) : mpf.ma.mul(pow[i / div[i]], pow[div[i]]); } long[] inv = mpf.ma.factorialInv(n); long[] a = new long[n + 1]; long[] b = new long[n + 1]; for (int i = 0; i <= n; i++) { a[i] = mpf.ma.mul(pow[i], inv[i]); b[i] = (i & 1) == 0 ? inv[i] : -inv[i]; } return mpf.mul(mpf.create(a), mpf.create(b), n).getCoefs(); } public static long[] bernoulli(int n, ModPolynomialFactory mpf) { long[] c = mpf.inv(mpf.create(java.util.Arrays.copyOfRange(mpf.ma.factorialInv(n + 1), 1, n + 2)), n).getCoefs(); long fac = 1; for (int i = 2; i <= n; i++) { fac = mpf.ma.mul(fac, i); c[i] = mpf.ma.mul(c[i], fac); } return mpf.create(c).getCoefs(); } } /** * @author https://atcoder.jp/users/suisen */ final class IntLongPair { public int fst; public long snd; public IntLongPair(final int fst, final long snd) {this.fst = fst; this.snd = snd;} @Override @SuppressWarnings("all") public boolean equals(final Object o) { if (this == o) return true; if (!(o instanceof IntLongPair)) return false; final IntLongPair p = (IntLongPair) o; return this.fst == p.fst && this.snd == p.snd; } @Override public int hashCode() {return Objects.hash(this.fst, this.snd);} @Override public String toString() {return "(" + this.fst + ", " + this.snd + ")";} } /** * @author https://atcoder.jp/users/suisen */ class FastScanner implements AutoCloseable { private final java.io.InputStream in; private final byte[] buf = new byte[2048]; private int ptr = 0; private int buflen = 0; public FastScanner(java.io.InputStream in) { this.in = in; } public FastScanner() { this(System.in); } private boolean hasNextByte() { if (ptr < buflen) return true; ptr = 0; try { buflen = in.read(buf); } catch (java.io.IOException e) { throw new RuntimeException(e); } return buflen > 0; } private int readByte() { return hasNextByte() ? buf[ptr++] : -1; } public boolean hasNext() { while (hasNextByte() && !(32 < buf[ptr] && buf[ptr] < 127)) ptr++; return hasNextByte(); } private StringBuilder nextSequence() { if (!hasNext()) throw new java.util.NoSuchElementException(); StringBuilder sb = new StringBuilder(); for (int b = readByte(); 32 < b && b < 127; b = readByte()) { sb.appendCodePoint(b); } return sb; } public String next() { return nextSequence().toString(); } public String next(int len) { return new String(nextChars(len)); } public char nextChar() { if (!hasNextByte()) throw new java.util.NoSuchElementException(); return (char) readByte(); } public char[] nextChars() { StringBuilder sb = nextSequence(); int l = sb.length(); char[] dst = new char[l]; sb.getChars(0, l, dst, 0); return dst; } public char[] nextChars(int len) { if (!hasNext()) throw new java.util.NoSuchElementException(); char[] s = new char[len]; int i = 0; int b = readByte(); while (32 < b && b < 127 && i < len) { s[i++] = (char) b; b = readByte(); } if (i != len) { throw new java.util.NoSuchElementException( String.format("Next token has smaller length than expected.", len) ); } return s; } public long nextLong() { if (!hasNext()) throw new java.util.NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) throw new NumberFormatException(); while (true) { if ('0' <= b && b <= '9') { n = n * 10 + b - '0'; } else if (b == -1 || !(32 < b && b < 127)) { return minus ? -n : n; } else throw new NumberFormatException(); b = readByte(); } } public int nextInt() { return Math.toIntExact(nextLong()); } public double nextDouble() { return Double.parseDouble(next()); } public void close() { try { in.close(); } catch (java.io.IOException e) { throw new RuntimeException(e); } } } /** * @author https://atcoder.jp/users/suisen * * 1. DESTRUCTIVE methods for int arrays. * 2. methods that receives arrays and return some results (except for int arrays). */ final class IntArrays { private IntArrays(){} public static void swap(final int[] a, final int u, final int v) { final int tmp = a[u]; a[u] = a[v]; a[v] = tmp; } public static void reverse(final int[] a, int begin, int end) { while (end - begin > 1) swap(a, begin++, --end); } public static void reverse(final int[] a) {reverse(a, 0, a.length);} public static void sortDescending(final int[] a) {Arrays.sort(a); reverse(a);} public static int fold(final int[] a, final IntBinaryOperator op) { int ret = a[0]; for (int i = 1; i < a.length; i++) ret = op.applyAsInt(ret, a[i]); return ret; } public static int sum(final int[] a) {return fold(a, Integer::sum);} public static int max(final int[] a) {return fold(a, Integer::max);} public static int min(final int[] a) {return fold(a, Integer::min);} public static IntPair maxWithIndex(final int[] a) { int max = max(a); return new IntPair(find(a, max), max); } public static IntPair minWithIndex(final int[] a) { int min = min(a); return new IntPair(find(a, min), min); } public static int find(final int[] a, final int v) { for (int i = 0; i < a.length; i++) if (a[i] == v) return i; return -1; } public static void map(final int[] a, final IntUnaryOperator op) {Arrays.setAll(a, i -> op.applyAsInt(a[i]));} public static int filter(final int[] src, final int[] dst, final IntPredicate p) { int idx = 0; for (final int e : src) if (p.test(e)) dst[idx++] = e; return idx; } public static int filterIndex(final int[] dst, final int beginIndex, final int endIndex, final IntPredicate p) { int idx = 0; for (int i = beginIndex; i < endIndex; i++) if (p.test(i)) dst[idx++] = i; return idx; } public static int filterIndex(final int dst[], final int endIndex, final IntPredicate p) { return filterIndex(dst, 0, endIndex, p); } public static void accumulate(final int[] a, final IntBinaryOperator op) { for (int i = 1; i < a.length; i++) a[i] = op.applyAsInt(a[i - 1], a[i]); } public static void accumulate(final int[] a) { for (int i = 1; i < a.length; i++) a[i] += a[i - 1]; } public static void permute(int[] p, int[] a) { int n = p.length; boolean[] settled = new boolean[n]; for (int i = 0; i < n; i++) { for (int j = i; !settled[j]; j = p[j]) { if (p[j] == i) { settled[j] = true; break; } int tmp = a[j]; a[j] = a[p[j]]; a[p[j]] = tmp; settled[j] = true; } } } public static void permute2(int[] p, int[] a, int[] b) { int n = p.length; boolean[] settled = new boolean[n]; for (int i = 0; i < n; i++) { for (int j = i; !settled[j]; j = p[j]) { if (p[j] == i) { settled[j] = true; break; } int tmp; tmp = a[j]; a[j] = a[p[j]]; a[p[j]] = tmp; tmp = b[j]; b[j] = b[p[j]]; b[p[j]] = tmp; settled[j] = true; } } } public static void permute3(int[] p, int[] a, int[] b, int[] c) { int n = p.length; boolean[] settled = new boolean[n]; for (int i = 0; i < n; i++) { for (int j = i; !settled[j]; j = p[j]) { if (p[j] == i) { settled[j] = true; break; } int tmp; tmp = a[j]; a[j] = a[p[j]]; a[p[j]] = tmp; tmp = b[j]; b[j] = b[p[j]]; b[p[j]] = tmp; tmp = c[j]; c[j] = c[p[j]]; c[p[j]] = tmp; settled[j] = true; } } } public static void permuteN(int[] p, int[]... as) { for (int[] a : as) permute(p, a); } public static int lowerBound(int[] sorted, int key) { int n = sorted.length; int l = -1, r = n; while (r - l > 1) { int m = (l + r) >> 1; if (sorted[m] < key) l = m; else r = m; } return r; } public static int upperBound(int[] sorted, int key) { int n = sorted.length; int l = -1, r = n; while (r - l > 1) { int m = (l + r) >> 1; if (sorted[m] <= key) l = m; else r = m; } return r; } public static int countRange(int[] sorted, int fromKey, int toKey) { return lowerBound(sorted, toKey) - lowerBound(sorted, fromKey); } public static int compare(final int[] a, final int[] b) { for (int i = 0; i < a.length; i++) { if (i >= b.length) return -1; if (a[i] > b[i]) return 1; if (a[i] < b[i]) return -1; } return a.length < b.length ? 1 : 0; } public static boolean equals(final int[] a, final int[] b) {return compare(a, b) == 0;} public static String join(final int[] a, final String sep) { final StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { sb.append(a[i]); if (i < a.length - 1) sb.append(sep); } return sb.toString(); } public static String joinWithPrefixAndSuffix(final int[] a, final IntFunction<String> idxToPre, final IntFunction<String> idxToSuf, final String sep) { final StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { sb.append(idxToPre.apply(i)).append(a[i]).append(idxToSuf.apply(i)); if (i < a.length - 1) sb.append(sep); } return sb.toString(); } } /** * @author https://atcoder.jp/users/suisen */ final class IntPair { public int fst, snd; public IntPair(final int fst, final int snd) {this.fst = fst; this.snd = snd;} @Override @SuppressWarnings("all") public boolean equals(final Object o) { if (this == o) return true; if (!(o instanceof IntPair)) return false; final IntPair p = (IntPair) o; return this.fst == p.fst && this.snd == p.snd; } @Override public int hashCode() { int hash = 1; hash = hash * 31 + fst; hash = hash * 31 + snd; return hash; } @Override public String toString() {return "(" + this.fst + ", " + this.snd + ")";} } /** * @author https://atcoder.jp/users/suisen */ final class MathUtil{ private MathUtil(){} public static IntArrayList primeList(int n) { IntArrayList primes = new IntArrayList(); int[] div = osak(n); for (int i = 2; i <= n; i++) { if (div[i] == i) primes.add(i); } return primes; } public static int[] osak(int n) { if (n <= 0) throw new AssertionError(); int[] div = new int[n + 1]; for (int i = 1; i <= n; i++) { if ((i & 1) != 0) { div[i] = i; } else { div[i] = 2; } } for (int i = 3; i <= n; i += 2) { if (div[i] == i) { if ((long) i * i > n) continue; for (int j = i * i; j <= n; j += i << 1) { div[j] = i; } } } return div; } public static java.util.HashMap<Long, Integer> factorize(long n) { java.util.HashMap<Long, Integer> factors = new java.util.HashMap<>(); for (long p = 2; p * p <= n; p++) { int q = 0; while (n % p == 0) { n /= p; q++; } if (q > 0) factors.put(p, q); } if (n > 1) factors.put(n, 1); return factors; } public static LongArrayList divisors(long n) { LongArrayList div = new LongArrayList(); for (long i = 1; i * i <= n; i++) { if (n % i == 0) { div.add(i); div.add(n / i); } } return div; } private static java.util.HashMap<Long, Integer> mergeFactor(java.util.HashMap<Long, Integer> fac1, java.util.HashMap<Long, Integer> fac2) { if (fac1.size() < fac2.size()) { return mergeFactor(fac2, fac1); } for (java.util.Map.Entry<Long, Integer> e : fac2.entrySet()) { long prime = e.getKey(); int num = e.getValue(); if (fac1.containsKey(prime)) { fac1.put(prime, Math.max(fac1.get(prime), num)); } else { fac1.put(prime, num); } } return fac1; } public static java.util.HashMap<Long, Integer> factorizedLCM(long a, long b) { return mergeFactor(factorize(a), factorize(b)); } public static java.util.HashMap<Long, Integer> factorizedLCM(long... xs) { java.util.HashMap<Long, Integer> lcm = new java.util.HashMap<>(); for (long x : xs) lcm = mergeFactor(lcm, factorize(x)); return lcm; } public static long lcm(long a, long b) { return (a / gcd(a, b)) * b; } public static long gcd(long a, long b) { a = Math.abs(a); b = Math.abs(b); if (a < b) { long tmp = a; a = b; b = tmp; } if (b == 0) return a; if (a == 0) return b; for (long r = a % b; r != 0; r = a % b) { a = b; b = r; } return b; } public static long gcd(long... xs) { long gcd = 0; for (long x : xs) gcd = gcd(gcd, x); return gcd; } /** * Return one of the solutions to {@code ax+by=gcd(a, b)}. * * @return {@code x}, {@code y}, {@code gcd(a, b)}. * @param a a of ax+by=gcd(a, b). * @param b b of ax+by=gcd(a, b). */ public static long[] extGCD(long a, long b) { long s = a, sx = 1, sy = 0; // ax + by = s long t = b, tx = 0, ty = 1; // ax + by = t for (long tmp, u, ux, uy; s % t != 0;) { // u: ax + by = s % t tmp = s / t; u = s - t * tmp; s = t ; t = u ; ux = sx - tx * tmp; sx = tx; tx = ux; uy = sy - ty * tmp; sy = ty; ty = uy; } return new long[]{tx, ty, a * tx + b * ty}; } public static long inv(long a, long MOD) { long b = MOD; long u = 1, v = 0; while (b > 0) { long t = a / b; a -= t * b; long tmp1 = a; a = b; b = tmp1; u -= t * v; long tmp2 = u; u = v; v = tmp2; } u %= MOD; return u < 0 ? u + MOD : u; } /** * @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g */ public static long[] gcdInv(long a, long mod) { if ((a %= mod) < 0) a += mod; if (a == 0) return new long[]{mod, 0}; long s = mod, t = a; long m0 = 0, m1 = 1; while (t > 0) { long u = s / t; s -= t * u; m0 -= m1 * u; long tmp; tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if (m0 < 0) m0 += mod / s; return new long[]{s, m0}; } public static long pow(long a, long b, long mod) { if (mod == 1) return 0; if ((a %= mod) < 0) a += mod; long pow = 1; for (long p = a, c = 1; b > 0;) { long lsb = b & -b; while (lsb != c) { c <<= 1; p = (p * p) % mod; } pow = (pow * p) % mod; b ^= lsb; } return pow; } public static java.util.OptionalLong sqrt(long a, long p) { if ((a %= p) < 0) a += p; if (a == 0) return java.util.OptionalLong.of(0); if (a == 1) return java.util.OptionalLong.of(1); if (pow(a, (p - 1) >> 1, p) != 1) return java.util.OptionalLong.empty(); if ((p & 3) == 3) { return java.util.OptionalLong.of(pow(a, (p + 1) >> 2, p)); } if ((p & 7) == 5) { if (pow(a, (p - 1) >> 2, p) == 1) { return java.util.OptionalLong.of(pow(a, (p + 3) >> 3, p)); } else { return java.util.OptionalLong.of(pow(2, (p - 1) >> 2, p) * pow(a, (p + 3) >> 3, p) % p); } } long S = 0; long Q = p - 1; while ((Q & 1) == 0) { ++S; Q >>= 1; } long z = 1; while (pow(z, (p - 1) >> 1, p) != p - 1) ++z; long c = pow(z, Q, p); long R = pow(a, (Q + 1) / 2, p); long t = pow(a, Q, p); long M = S; while (t != 1) { long cur = t; int i; for (i = 1; i < M; i++) { cur = cur * cur % p; if (cur == 1) break; } long b = pow(c, 1l << (M - i - 1), p); R = R * b % p; t = t * b % p * b % p; c = b * b % p; M = i; } return java.util.OptionalLong.of(R); } public static long eulerPhi(long n) { for (long p : factorize(n).keySet()) { n = (n / p) * (p - 1); } return n; } public static long comb(long n, long r) { if (n < r) return 0; r = Math.min(r, n - r); long res = 1; for (long d = 1; d <= r; d++) {res *= n--; res /= d;} return res; } public static long ceilSqrt(long n) { long l = -1, r = n; while (r - l > 1) { long m = (r + l) >> 1; if (m * m >= n) r = m; else l = m; } return r; } public static long floorSqrt(long n) { long l = 0, r = n + 1; while (r - l > 1) { long m = (r + l) >> 1; if (m * m > n) r = m; else l = m; } return l; } public static long[] crt(long[] r, long[] m){ if (r.length != m.length) { throw new AssertionError("Different length."); } int n = r.length; long r0 = 0, m0 = 1; for(int i=0; i<n; i++){ if (m[i] < 1) { throw new AssertionError(); } long m1 = m[i]; long r1 = r[i] % m1; if (r1 < 0) r1 += m1; if (m0 < m1){ long tmp; 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; } long[] gi = gcdInv(m0, m1); long g = gi[0], im = gi[1]; long u1 = m1 / g; if((r1 - r0) % g != 0) return new long[]{0, 0}; long x = (r1 - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; if (r0 < 0) r0 += m0; } return new long[]{r0, m0}; } public static long garner(long[] c, long[] mods) { int n = c.length + 1; long[] cnst = new long[n]; long[] coef = new long[n]; java.util.Arrays.fill(coef, 1); for (int i = 0; i < n - 1; i++) { long m1 = mods[i]; long v = (c[i] - cnst[i] + m1) % m1; v = v * pow(coef[i], m1 - 2, m1) % m1; for (int j = i + 1; j < n; j++) { long m2 = mods[j]; cnst[j] = (cnst[j] + coef[j] * v) % m2; coef[j] = (coef[j] * m1) % m2; } } return cnst[n - 1]; } public static long floorSum(long n, 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; } long ymax = (a * n + b) / m; long xmax = ymax * m - b; if (ymax == 0) return ans; ans += (n - (xmax + a - 1) / a) * ymax; ans += floorSum(ymax, a, m, (a - xmax % a) % a); return ans; } /** * @param m prime */ public static int primitiveRoot(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 = 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 (pow(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) return g; } } } class Const { public static final long LINF = 1l << 59; public static final int IINF = (1 << 30) - 1; public static final double DINF = 1e150; public static final double SMALL = 1e-12; public static final double MEDIUM = 1e-9; public static final double LARGE = 1e-6; public static final long MOD1000000007 = 1000000007; public static final long MOD998244353 = 998244353 ; public static final long MOD754974721 = 754974721 ; public static final long MOD167772161 = 167772161 ; public static final long MOD469762049 = 469762049 ; public static final int[] dx8 = {1, 0, -1, 0, 1, -1, -1, 1}; public static final int[] dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; public static final int[] dx4 = {1, 0, -1, 0}; public static final int[] dy4 = {0, 1, 0, -1}; } interface Convolution { static final int THRESHOLD_NAIVE_CONVOLUTION = 150; public static final Convolution C_167772161 = new Convolution167772161(); public static final Convolution C_469762049 = new Convolution469762049(); public static final Convolution C_754974721 = new Convolution754974721(); public static final Convolution C_998244353 = new Convolution998244353(); public long[] convolution(long[] a, long[] b); public static Convolution of(int mod) { if (mod == 998244353) { return C_998244353; } else if (mod == 167772161) { return C_167772161; } else if (mod == 469762049) { return C_469762049; } else if (mod == 754974721) { return C_754974721; } else { return new ConvolutionAnyMod(mod); } } public static Convolution ofNTTPrime(int mod) { if (mod == 998244353) { return C_998244353; } else if (mod == 167772161) { return C_167772161; } else if (mod == 469762049) { return C_469762049; } else if (mod == 754974721) { return C_754974721; } else { return new ConvolutionNTTPrime(mod); } } public static long[] convolutionNaive(long[] a, long[] b, int mod) { int n = a.length; int m = b.length; int k = n + m - 1; 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; } for (int i = 0; i < k; i++) { ret[i] %= mod; } return ret; } private static int ceilPow2(int n) { int x = 0; while ((1L << x) < n) x++; return x; } /** * Pre-calculation for NTT. * * @param mod NTT Prime. * @param g Primitive root of mod. * @return Pre-calculation table. */ private static long[] sumE(int mod, int g) { long[] sum_e = new long[30]; long[] es = new long[30]; long[] ies = new long[30]; int cnt2 = Integer.numberOfTrailingZeros(mod - 1); long e = MathUtil.pow(g, (mod - 1) >> cnt2, mod); long ie = MathUtil.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(int mod, int g) { long[] sum_ie = new long[30]; long[] es = new long[30]; long[] ies = new long[30]; int cnt2 = Integer.numberOfTrailingZeros(mod - 1); long e = MathUtil.pow(g, (mod - 1) >> cnt2, mod); long ie = MathUtil.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; } static final class Convolution754974721 implements Convolution { private static final int PRIMITIVE_ROOT = 11; private static final int NTT_PRIME = 754974721; @Override public long[] convolution(long[] a, long[] b) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; if (Math.max(n, m) <= THRESHOLD_NAIVE_CONVOLUTION) { int k = n + m - 1; 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] % NTT_PRIME; } for (int i = 0; i < k; i++) { ret[i] %= NTT_PRIME; } return ret; } int z = 1 << ceilPow2(n + m - 1); { long[] na = new long[z]; long[] nb = new long[z]; System.arraycopy(a, 0, na, 0, n); System.arraycopy(b, 0, nb, 0, m); a = na; b = nb; } long[] sume = sumE(NTT_PRIME, PRIMITIVE_ROOT); long[] sumie = sumIE(NTT_PRIME, PRIMITIVE_ROOT); butterfly(a, sume); butterfly(b, sume); for (int i = 0; i < z; i++) { a[i] = a[i] * b[i] % NTT_PRIME; } butterflyInv(a, sumie); a = java.util.Arrays.copyOf(a, n + m - 1); long iz = MathUtil.pow(z, NTT_PRIME - 2, NTT_PRIME); for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % NTT_PRIME; return a; } private void butterfly(long[] a, long[] sumE) { int h = ceilPow2(a.length); for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1), p = 1 << (h - ph); long now = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p] * now % NTT_PRIME; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (l - r + NTT_PRIME) % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); now = now * sumE[x] % NTT_PRIME; } } } private void butterflyInv(long[] a, long[] sumIE) { int h = ceilPow2(a.length); for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); long inow = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p]; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (NTT_PRIME + l - r) * inow % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); inow = inow * sumIE[x] % NTT_PRIME; } } } } static final class Convolution167772161 implements Convolution { private static final int PRIMITIVE_ROOT = 3; private static final int NTT_PRIME = 167772161; public long[] convolution(long[] a, long[] b) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; if (Math.max(n, m) <= THRESHOLD_NAIVE_CONVOLUTION) { int k = n + m - 1; 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] % NTT_PRIME; } for (int i = 0; i < k; i++) { ret[i] %= NTT_PRIME; } return ret; } int z = 1 << ceilPow2(n + m - 1); { long[] na = new long[z]; long[] nb = new long[z]; System.arraycopy(a, 0, na, 0, n); System.arraycopy(b, 0, nb, 0, m); a = na; b = nb; } long[] sume = sumE(NTT_PRIME, PRIMITIVE_ROOT); long[] sumie = sumIE(NTT_PRIME, PRIMITIVE_ROOT); butterfly(a, sume); butterfly(b, sume); for (int i = 0; i < z; i++) { a[i] = a[i] * b[i] % NTT_PRIME; } butterflyInv(a, sumie); a = java.util.Arrays.copyOf(a, n + m - 1); long iz = MathUtil.pow(z, NTT_PRIME - 2, NTT_PRIME); for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % NTT_PRIME; return a; } private void butterfly(long[] a, long[] sumE) { int h = ceilPow2(a.length); for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1), p = 1 << (h - ph); long now = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p] * now % NTT_PRIME; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (l - r + NTT_PRIME) % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); now = now * sumE[x] % NTT_PRIME; } } } private void butterflyInv(long[] a, long[] sumIE) { int h = ceilPow2(a.length); for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); long inow = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p]; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (NTT_PRIME + l - r) * inow % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); inow = inow * sumIE[x] % NTT_PRIME; } } } } static final class Convolution469762049 implements Convolution { private static final int PRIMITIVE_ROOT = 3; private static final int NTT_PRIME = 469762049; public long[] convolution(long[] a, long[] b) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; if (Math.max(n, m) <= THRESHOLD_NAIVE_CONVOLUTION) { int k = n + m - 1; 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] % NTT_PRIME; } for (int i = 0; i < k; i++) { ret[i] %= NTT_PRIME; } return ret; } int z = 1 << ceilPow2(n + m - 1); { long[] na = new long[z]; long[] nb = new long[z]; System.arraycopy(a, 0, na, 0, n); System.arraycopy(b, 0, nb, 0, m); a = na; b = nb; } long[] sume = sumE(NTT_PRIME, PRIMITIVE_ROOT); long[] sumie = sumIE(NTT_PRIME, PRIMITIVE_ROOT); butterfly(a, sume); butterfly(b, sume); for (int i = 0; i < z; i++) { a[i] = a[i] * b[i] % NTT_PRIME; } butterflyInv(a, sumie); a = java.util.Arrays.copyOf(a, n + m - 1); long iz = MathUtil.pow(z, NTT_PRIME - 2, NTT_PRIME); for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % NTT_PRIME; return a; } private void butterfly(long[] a, long[] sumE) { int h = ceilPow2(a.length); for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1), p = 1 << (h - ph); long now = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p] * now % NTT_PRIME; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (l - r + NTT_PRIME) % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); now = now * sumE[x] % NTT_PRIME; } } } private void butterflyInv(long[] a, long[] sumIE) { int h = ceilPow2(a.length); for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); long inow = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p]; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (NTT_PRIME + l - r) * inow % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); inow = inow * sumIE[x] % NTT_PRIME; } } } } static class Convolution998244353 implements Convolution { private static final int PRIMITIVE_ROOT = 3; private static final int NTT_PRIME = 998244353; public long[] convolution(long[] a, long[] b) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; if (Math.max(n, m) <= THRESHOLD_NAIVE_CONVOLUTION) { int k = n + m - 1; 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] % NTT_PRIME; } for (int i = 0; i < k; i++) { ret[i] %= NTT_PRIME; } return ret; } int z = 1 << ceilPow2(n + m - 1); { long[] na = new long[z]; long[] nb = new long[z]; System.arraycopy(a, 0, na, 0, n); System.arraycopy(b, 0, nb, 0, m); a = na; b = nb; } long[] sume = sumE(NTT_PRIME, PRIMITIVE_ROOT); long[] sumie = sumIE(NTT_PRIME, PRIMITIVE_ROOT); butterfly(a, sume); butterfly(b, sume); for (int i = 0; i < z; i++) { a[i] = a[i] * b[i] % NTT_PRIME; } butterflyInv(a, sumie); a = java.util.Arrays.copyOf(a, n + m - 1); long iz = MathUtil.pow(z, NTT_PRIME - 2, NTT_PRIME); for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % NTT_PRIME; return a; } private void butterfly(long[] a, long[] sumE) { int h = ceilPow2(a.length); for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1), p = 1 << (h - ph); long now = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p] * now % NTT_PRIME; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (l - r + NTT_PRIME) % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); now = now * sumE[x] % NTT_PRIME; } } } private void butterflyInv(long[] a, long[] sumIE) { int h = ceilPow2(a.length); for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); long inow = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p]; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (NTT_PRIME + l - r) * inow % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); inow = inow * sumIE[x] % NTT_PRIME; } } } } static final class ConvolutionAnyMod implements Convolution { private final int MOD; private ConvolutionAnyMod(int mod) { this.MOD = mod; } public long[] convolution(long[] a, long[] b) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; if (Math.max(n, m) <= THRESHOLD_NAIVE_CONVOLUTION) { int k = n + m - 1; 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; } for (int i = 0; i < k; i++) { ret[i] %= MOD; } return ret; } int mod1 = 754974721; int mod2 = 167772161; int mod3 = 469762049; long[] c1 = C_754974721.convolution(a, b); long[] c2 = C_167772161.convolution(a, b); long[] c3 = C_469762049.convolution(a, b); int retSize = c1.length; long[] ret = new long[retSize]; long[] mods = {mod1, mod2, mod3, MOD}; for (int i = 0; i < retSize; ++i) { ret[i] = MathUtil.garner(new long[]{c1[i], c2[i], c3[i]}, mods); } return ret; } } static final class ConvolutionNTTPrime implements Convolution { private final int NTT_PRIME; private final int PRIMITIVE_ROOT; private ConvolutionNTTPrime(int mod) { this.NTT_PRIME = mod; this.PRIMITIVE_ROOT = MathUtil.primitiveRoot(mod); } public long[] convolution(long[] a, long[] b) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; if (Math.max(n, m) <= THRESHOLD_NAIVE_CONVOLUTION) { int k = n + m - 1; 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] % NTT_PRIME; } for (int i = 0; i < k; i++) { ret[i] %= NTT_PRIME; } return ret; } int z = 1 << ceilPow2(n + m - 1); { long[] na = new long[z]; long[] nb = new long[z]; System.arraycopy(a, 0, na, 0, n); System.arraycopy(b, 0, nb, 0, m); a = na; b = nb; } long[] sume = sumE(NTT_PRIME, PRIMITIVE_ROOT); long[] sumie = sumIE(NTT_PRIME, PRIMITIVE_ROOT); butterfly(a, sume); butterfly(b, sume); for (int i = 0; i < z; i++) { a[i] = a[i] * b[i] % NTT_PRIME; } butterflyInv(a, sumie); a = java.util.Arrays.copyOf(a, n + m - 1); long iz = MathUtil.pow(z, NTT_PRIME - 2, NTT_PRIME); for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % NTT_PRIME; return a; } private void butterflyInv(long[] a, long[] sumIE) { int n = a.length; int h = ceilPow2(n); for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); long inow = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p]; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (NTT_PRIME + l - r) * inow % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); inow = inow * sumIE[x] % NTT_PRIME; } } } private void butterfly(long[] a, long[] sumE) { int n = a.length; int h = ceilPow2(n); for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1), p = 1 << (h - ph); long now = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p] * now % NTT_PRIME; a[i + offset] = (l + r) % NTT_PRIME; a[i + offset + p] = (l - r + NTT_PRIME) % NTT_PRIME; } int x = Integer.numberOfTrailingZeros(~s); now = now * sumE[x] % NTT_PRIME; } } } } } /** * @author https://atcoder.jp/users/suisen */ interface ModArithmetic { public static ModArithmetic of(long mod) { if (mod <= 0) { throw new IllegalArgumentException("Negative mod"); } else if (mod == 1) { return new ModArithmetic1(); } else if (mod == 2) { return new ModArithmetic2(); } else if (mod == 1000000007) { return new ModArithmetic1000000007(); } else if (mod == 998244353) { return new ModArithmetic998244353(); } else { return new ModArithmeticDynamic(mod); // return new ModArithmeticBarrett(mod); } } public long getMod(); public long mod(long a); public long add(long a, long b); public long sub(long a, long b); public long mul(long a, long b); public long inv(long a); public long pow(long a, long b); public default long add(long a, long b, long c) { return add(a, add(b, c)); } public default long add(long a, long b, long c, long d) { return add(a, add(b, add(c, d))); } public default long add(long a, long b, long c, long d, long e) { return add(a, add(b, add(c, add(d, e)))); } public default long add(long a, long b, long c, long d, long e, long f) { return add(a, add(b, add(c, add(d, add(e, f))))); } public default long add(long a, long b, long c, long d, long e, long f, long g) { return add(a, add(b, add(c, add(d, add(e, add(f, g)))))); } public default long add(long a, long b, long c, long d, long e, long f, long g, long h) { return add(a, add(b, add(c, add(d, add(e, add(f, add(g, h))))))); } public default long add(long... xs) { long s = 0; for (long x : xs) s += x; return mod(s); } public default long mul(long a, long b, long c) { return mul(a, mul(b, c)); } public default long mul(long a, long b, long c, long d) { return mul(a, mul(b, mul(c, d))); } public default long mul(long a, long b, long c, long d, long e) { return mul(a, mul(b, mul(c, mul(d, e)))); } public default long mul(long a, long b, long c, long d, long e, long f) { return mul(a, mul(b, mul(c, mul(d, mul(e, f))))); } public default long mul(long a, long b, long c, long d, long e, long f, long g) { return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, g)))))); } public default long mul(long a, long b, long c, long d, long e, long f, long g, long h) { return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, mul(g, h))))))); } public default long mul(long... xs) { long s = 1; for (long x : xs) s = mul(s, x); return s; } public default long div(long a, long b) { return mul(a, inv(b)); } public default java.util.OptionalLong sqrt(long a) { a = mod(a); if (a == 0) return java.util.OptionalLong.of(0); if (a == 1) return java.util.OptionalLong.of(1); long p = getMod(); if (pow(a, (p - 1) >> 1) != 1) return java.util.OptionalLong.empty(); if ((p & 3) == 3) { return java.util.OptionalLong.of(pow(a, (p + 1) >> 2)); } if ((p & 7) == 5) { if (pow(a, (p - 1) >> 2) == 1) { return java.util.OptionalLong.of(pow(a, (p + 3) >> 3)); } else { return java.util.OptionalLong.of(mul(pow(2, (p - 1) >> 2), pow(a, (p + 3) >> 3))); } } long S = 0; long Q = p - 1; while ((Q & 1) == 0) { ++S; Q >>= 1; } long z = 1; while (pow(z, (p - 1) >> 1) != p - 1) ++z; long c = pow(z, Q); long R = pow(a, (Q + 1) / 2); long t = pow(a, Q); long M = S; while (t != 1) { long cur = t; int i; for (i = 1; i < M; i++) { cur = mul(cur, cur); if (cur == 1) break; } long b = pow(c, 1l << (M - i - 1)); R = mul(R, b); t = mul(t, b, b); c = mul(b, b); M = i; } return java.util.OptionalLong.of(R); } /** array operations */ public default long[] rangeInv(int n) { final long MOD = getMod(); if (n >= MOD) throw new ArithmeticException("divide by zero"); long[] invs = new long[n + 1]; invs[1] = 1; for (int i = 2; i <= n; i++) { long q = MOD - MOD / i; long r = invs[(int) (MOD % i)]; invs[i] = mul(q, r); } return invs; } public default long[] arrayInv(long[] a) { int n = a.length; long[] dp = new long[n + 1]; long[] pd = new long[n + 1]; dp[0] = pd[n] = 1; for (int i = 0; i < n; i++) dp[i + 1] = mul(dp[i], a[i ]); for (int i = n; i > 0; i--) pd[i - 1] = mul(pd[i], a[i - 1]); long inv = inv(dp[n]); long[] invs = new long[n]; for (int i = 0; i < n; i++) { long lr = mul(dp[i], pd[i + 1]); invs[i] = mul(lr, inv); } return invs; } public default long[] factorial(int n) { long[] ret = new long[n + 1]; ret[0] = 1; for (int i = 1; i <= n; i++) ret[i] = mul(ret[i - 1], i); return ret; } public default long[] factorialInv(int n) { long facN = 1; for (int i = 2; i <= n; i++) facN = mul(facN, i); long[] invs = new long[n + 1]; invs[n] = inv(facN); for (int i = n; i > 0; i--) invs[i - 1] = mul(invs[i], i); return invs; } public default long[] rangePower(long a, int n) { a = mod(a); long[] pows = new long[n + 1]; pows[0] = 1; for (int i = 1; i <= n; i++) pows[i] = mul(pows[i - 1], a); return pows; } /** combinatric operations */ public default long[][] combTable(int n) { long[][] comb = new long[n + 1][]; for (int i = 0; i <= n; i++) { comb[i] = new long[i + 1]; comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; j++) { comb[i][j] = add(comb[i - 1][j - 1], comb[i - 1][j]); } } return comb; } public default long comb(int n, int r, long[] factorial, long[] invFactorial) { if (r < 0 || r > n) return 0; long inv = mul(invFactorial[r], invFactorial[n - r]); return mul(factorial[n], inv); } public default long naiveComb(long n, long r) { if (r < 0 || r > n) return 0; r = Math.min(r, n - r); long res = 1; long[] invs = rangeInv(Math.toIntExact(r)); for (int d = 1; d <= r; d++) { res = mul(res, n--, invs[d]); } return res; } public default long perm(int n, int r, long[] factorial, long[] invFactorial) { if (r < 0 || r > n) return 0; return mul(factorial[n], invFactorial[n - r]); } public default long naivePerm(long n, long r) { if (r < 0 || r > n) return 0; long res = 1; for (long i = n - r + 1; i <= n; i++) res = mul(res, i); return res; } static final class ModArithmetic1 implements ModArithmetic { @Override public long getMod() {return 1;} @Override public long mod(long a) {return 0;} @Override public long add(long a, long b) {return 0;} @Override public long sub(long a, long b) {return 0;} @Override public long mul(long a, long b) {return 0;} @Override public long inv(long a) {return 0;} @Override public long pow(long a, long b) {return 0;} @Override public long[] rangeInv(int n) {return new long[n + 1];} @Override public long[] arrayInv(long[] a) {return new long[a.length];} @Override public long[] factorial(int n) {return new long[n + 1];} @Override public long[] factorialInv(int n) {return new long[n + 1];} @Override public long[] rangePower(long a, int n) {return new long[n + 1];} @Override public long[][] combTable(int n) {return new long[n + 1][n + 1];} @Override public long comb(int n, int r, long[] factorial, long[] invFactorial) {return 0;} @Override public long naiveComb(long n, long r) {return 0;} @Override public long perm(int n, int r, long[] factorial, long[] invFactorial) {return 0;} @Override public long naivePerm(long n, long r) {return 0;} } static final class ModArithmetic2 implements ModArithmetic { @Override public long getMod() {return 2;} @Override public long mod(long a) {return a & 1;} @Override public long add(long a, long b) {return (a ^ b) & 1;} @Override public long sub(long a, long b) {return (a ^ b) & 1;} @Override public long mul(long a, long b) {return (a & b) & 1;} @Override public long inv(long a) { if ((a & 1) == 1) return 1; throw new ArithmeticException("divide by zero"); } @Override public long pow(long a, long b) { if (b == 0 || (a & 1) == 1) return 1; return 0; } } static final class ModArithmetic1000000007 implements ModArithmetic { private static final long MOD = Const.MOD1000000007; @Override public long getMod() {return MOD;} @Override public long mod(long a) {return (a %= MOD) < 0 ? a + MOD : a;} @Override public long add(long a, long b) { long s = a + b; return s >= MOD ? s - MOD : s; } @Override public long sub(long a, long b) { long s = a - b; return s < 0 ? s + MOD : s; } @Override public long mul(long a, long b) { return (a * b) % MOD; } @Override public long inv(long a) { a = mod(a); long b = MOD; long u = 1, v = 0; while (b >= 1) { long t = a / b; a -= t * b; long tmp1 = a; a = b; b = tmp1; u -= t * v; long tmp2 = u; u = v; v = tmp2; } // if (a != 1) throw new ArithmeticException("divide by zero"); return mod(u); } @Override public long pow(long a, long b) { a = mod(a); long pow = 1; for (long p = a, c = 1; b > 0;) { long lsb = b & -b; while (lsb != c) { c <<= 1; p = (p * p) % MOD; } pow = (pow * p) % MOD; b ^= lsb; } return pow; } } static final class ModArithmetic998244353 implements ModArithmetic { private static final long MOD = Const.MOD998244353; @Override public long getMod() {return MOD;} @Override public long mod(long a) {return (a %= MOD) < 0 ? a + MOD : a;} @Override public long add(long a, long b) { long s = a + b; return s >= MOD ? s - MOD : s; } @Override public long sub(long a, long b) { long s = a - b; return s < 0 ? s + MOD : s; } @Override public long mul(long a, long b) { return (a * b) % MOD; } @Override public long inv(long a) { a = mod(a); long b = MOD; long u = 1, v = 0; while (b >= 1) { long t = a / b; a -= t * b; long tmp1 = a; a = b; b = tmp1; u -= t * v; long tmp2 = u; u = v; v = tmp2; } // if (a != 1) throw new ArithmeticException("divide by zero"); return mod(u); } @Override public long pow(long a, long b) { a = mod(a); long pow = 1; for (long p = a, c = 1; b > 0;) { long lsb = b & -b; while (lsb != c) { c <<= 1; p = (p * p) % MOD; } pow = (pow * p) % MOD; b ^= lsb; } return pow; } } static class ModArithmeticDynamic implements ModArithmetic { final long MOD; private ModArithmeticDynamic(long mod) { this.MOD = mod; } @Override public long getMod() { return MOD; } @Override public long mod(long a) { return (a %= MOD) < 0 ? a + MOD : a; } @Override public long add(long a, long b) { long s = a + b; return s >= MOD ? s - MOD : s; } @Override public long sub(long a, long b) { long s = a - b; return s < 0 ? s + MOD : s; } @Override public long mul(long a, long b) { return (a * b) % MOD; } @Override public long inv(long a) { a = mod(a); long b = MOD; long u = 1, v = 0; while (b >= 1) { long t = a / b; a -= t * b; long tmp1 = a; a = b; b = tmp1; u -= t * v; long tmp2 = u; u = v; v = tmp2; } // if (a != 1) throw new ArithmeticException("divide by zero"); return mod(u); } @Override public long pow(long a, long b) { a = mod(a); long pow = 1; for (long p = a, c = 1; b > 0;) { long lsb = b & -b; while (lsb != c) { c <<= 1; p = mul(p, p); } pow = mul(pow, p); b ^= lsb; } return pow; } } static final class ModArithmeticBarrett extends ModArithmeticDynamic { private static final long mask = 0xffff_ffffl; private final long mh; private final long ml; private ModArithmeticBarrett(long mod) { super(mod); long a = (1l << 32) / mod, b = (1l << 32) % mod; long m = a * a * mod + 2 * a * b + (b * b) / mod; this.mh = m >>> 32; this.ml = m & mask; } private long reduce(long x) { long z = (x & mask) * ml; z = (x & mask) * mh + (x >>> 32) * ml + (z >>> 32); z = (x >>> 32) * mh + (z >>> 32); x -= z * MOD; return (int) (x < MOD ? x : x - MOD); } @Override public long mul(long a, long b) { return reduce(a * b); } } }