結果
問題 | No.1092 modular arithmetic |
ユーザー | shun_skycrew |
提出日時 | 2022-09-17 16:22:06 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 29,643 bytes |
コンパイル時間 | 3,343 ms |
コンパイル使用メモリ | 94,144 KB |
実行使用メモリ | 63,004 KB |
最終ジャッジ日時 | 2024-06-01 15:13:30 |
合計ジャッジ時間 | 11,000 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 66 ms
51,104 KB |
testcase_01 | AC | 121 ms
54,648 KB |
testcase_02 | AC | 66 ms
50,668 KB |
testcase_03 | AC | 179 ms
57,392 KB |
testcase_04 | AC | 173 ms
57,556 KB |
testcase_05 | AC | 175 ms
57,572 KB |
testcase_06 | AC | 153 ms
57,528 KB |
testcase_07 | AC | 174 ms
57,256 KB |
testcase_08 | AC | 172 ms
57,436 KB |
testcase_09 | AC | 159 ms
57,388 KB |
testcase_10 | AC | 152 ms
57,340 KB |
testcase_11 | AC | 157 ms
57,408 KB |
testcase_12 | AC | 150 ms
57,168 KB |
testcase_13 | AC | 114 ms
54,444 KB |
testcase_14 | AC | 120 ms
54,248 KB |
testcase_15 | AC | 94 ms
52,092 KB |
testcase_16 | AC | 112 ms
54,348 KB |
testcase_17 | AC | 105 ms
54,756 KB |
testcase_18 | AC | 154 ms
57,388 KB |
testcase_19 | AC | 158 ms
57,480 KB |
testcase_20 | AC | 177 ms
57,504 KB |
testcase_21 | AC | 168 ms
57,476 KB |
testcase_22 | AC | 179 ms
57,616 KB |
testcase_23 | AC | 240 ms
62,696 KB |
testcase_24 | AC | 136 ms
57,572 KB |
testcase_25 | AC | 217 ms
59,816 KB |
testcase_26 | AC | 242 ms
62,836 KB |
testcase_27 | AC | 102 ms
54,552 KB |
testcase_28 | AC | 201 ms
59,920 KB |
testcase_29 | AC | 258 ms
63,004 KB |
testcase_30 | AC | 208 ms
59,680 KB |
testcase_31 | AC | 99 ms
54,256 KB |
testcase_32 | AC | 194 ms
59,428 KB |
ソースコード
import java.util.*; import java.io.*; import java.math.*; import java.util.function.*; final class FastInputStream { private static final int BUF_SIZE = 1 << 14; private final InputStream in; private final byte buf[] = new byte[BUF_SIZE]; private int pos = 0; private int count = 0; private static final int TOKEN_SIZE = 1 << 20; private final byte tokenBuf[] = new byte[TOKEN_SIZE]; public FastInputStream(final InputStream in) { this.in = in; } private final void readBuf() { pos = 0; try { count = in.read(buf); } catch(IOException e) { e.printStackTrace(); } } private final boolean hasNextByte() { if(pos < count) return true; readBuf(); return count > 0; } private final byte read() { if(hasNextByte()) return buf[pos ++]; else throw new NoSuchElementException(); } private final boolean isPrintableChar(final byte c) { return 33 <= c && c <= 126; } private final boolean isNumber(final byte c) { return 48 <= c && c <= 57; } private final void skipUnprintable() { while(true) { for(int i = pos; i < count; i ++) { if(isPrintableChar(buf[i])) { pos = i; return; } } readBuf(); if(count <= 0) throw new NoSuchElementException(); } } private final boolean readEOL() { if(!hasNextByte()) return true; if(buf[pos] == 13) { pos ++; if(hasNextByte() && buf[pos] == 10) pos ++; return true; } if(buf[pos] == 10) { pos ++; return true; } return false; } public final char nextChar() { skipUnprintable(); return (char)buf[pos ++]; } public final String next() { skipUnprintable(); int tokenCount = 0; outer: while(count > 0) { for(int i = pos; i < count; i ++) { final byte b = buf[i]; if(!isPrintableChar(b)) { pos = i; break outer; } tokenBuf[tokenCount ++] = b; } readBuf(); } return new String(tokenBuf, 0, tokenCount); } public final String nextLine() { readEOL(); if(!hasNextByte()) throw new NoSuchElementException(); int tokenCount = 0; while(!readEOL()) tokenBuf[tokenCount ++] = read(); return new String(tokenBuf, 0, tokenCount); } public final int nextInt() { skipUnprintable(); int n = 0; boolean minus = false; if(buf[pos] == 45) { minus = true; pos ++; if(!hasNextByte() || !isNumber(buf[pos])) throw new InputMismatchException(); } outer: while(count > 0) { for(int i = pos; i < count; i ++) { final byte b = buf[i]; if(!isPrintableChar(b)) { pos = i; break outer; } if(!isNumber(b)) throw new InputMismatchException(); if(minus) { if(n < - 214748364) throw new ArithmeticException("int overflow"); if(n == - 214748364 && b > 56) throw new ArithmeticException("int overflow"); n = (n << 3) + (n << 1) + 48 - b; }else { if(n > 214748364) throw new ArithmeticException("int overflow"); if(n == 214748364 && b >= 56) throw new ArithmeticException("int overflow"); n = (n << 3) + (n << 1) - 48 + b; } } readBuf(); } return n; } public final long nextLong() { skipUnprintable(); long n = 0; boolean minus = false; if(buf[pos] == 45) { minus = true; pos ++; if(!hasNextByte() || !isNumber(buf[pos])) throw new InputMismatchException(); } outer: while(count > 0) { for(int i = pos; i < count; i ++) { final byte b = buf[i]; if(!isPrintableChar(b)) { pos = i; break outer; } if(!isNumber(b)) throw new InputMismatchException(); if(minus) { if(n < - 922337203685477580l) throw new ArithmeticException("long overflow"); if(n == - 922337203685477580l && b > 56) throw new ArithmeticException("long overflow"); n = (n << 3) + (n << 1) + 48 - b; }else { if(n > 922337203685477580l) throw new ArithmeticException("long overflow"); if(n == 922337203685477580l && b >= 56) throw new ArithmeticException("long overflow"); n = (n << 3) + (n << 1) - 48 + b; } } readBuf(); } return n; } public final double nextDouble() { return Double.parseDouble(next()); } public final void close() { try { in.close(); } catch(IOException e) { e.printStackTrace(); } } } final class FastOutputStream { private static final int BUF_SIZE = 1 << 13; private final byte buf[] = new byte[BUF_SIZE]; private final OutputStream out; private int count = 0; private static final byte TRUE_BYTES[] = {116, 114, 117, 101}; private static final byte FALSE_BYTES[] = {102, 97, 108, 115, 101}; private static final byte INT_MIN_BYTES[] = {45, 50, 49, 52, 55, 52, 56, 51, 54, 52, 56}; private static final byte LONG_MIN_BYTES[] = {45, 57, 50, 50, 51, 51, 55, 50, 48, 51, 54, 56, 53, 52, 55, 55, 53, 56, 48, 56}; private static final int TOKEN_SIZE = 20; private final byte tokenBuf[] = new byte[TOKEN_SIZE]; private static final int PRECISION = 10; public FastOutputStream(OutputStream out) { this.out = out; } public final void print() { } public final void write(final byte b) { if(count == BUF_SIZE) internalFlush(); buf[count ++] = b; } public final void print(final char c) { write((byte) c); } public final void print(final boolean b) { if(b) { if(count + 4 > BUF_SIZE) internalFlush(); System.arraycopy(TRUE_BYTES, 0, buf, count, TRUE_BYTES.length); count += TRUE_BYTES.length; }else { if(count + 5 > BUF_SIZE) internalFlush(); System.arraycopy(FALSE_BYTES, 0, buf, count, FALSE_BYTES.length); count += FALSE_BYTES.length; } } public final void print(int x) { if(count + 11 > BUF_SIZE) internalFlush(); if(x == Integer.MIN_VALUE) { System.arraycopy(INT_MIN_BYTES, 0, buf, count, INT_MIN_BYTES.length); count += INT_MIN_BYTES.length; return; } if(x == 0) { buf[count ++] = 48; return; } if(x < 0) { buf[count ++] = 45; x = - x; } int tokenCount = 11; while(x > 0) { final int y = x / 10; tokenBuf[-- tokenCount] = (byte) (x - (y << 3) - (y << 1) + 48); x = y; } System.arraycopy(tokenBuf, tokenCount, buf, count, 11 - tokenCount); count += 11 - tokenCount; } public final void print(long x) { if(count + 20 > BUF_SIZE) internalFlush(); if(x == Long.MIN_VALUE) { System.arraycopy(LONG_MIN_BYTES, 0, buf, count, LONG_MIN_BYTES.length); count += LONG_MIN_BYTES.length; return; } if(x == 0) { buf[count ++] = 48; return; } if(x < 0) { buf[count ++] = 45; x = - x; } int tokenCount = 20; while(x > 0) { final long y = x / 10; tokenBuf[-- tokenCount] = (byte) (x - (y << 3) - (y << 1) + 48); x = y; } System.arraycopy(tokenBuf, tokenCount, buf, count, 20 - tokenCount); count += 20 - tokenCount; } public final void print(final double d) { print(d, PRECISION); } public final void print(double d, final int precision) { if(count == BUF_SIZE) internalFlush(); if(d < 0) { buf[count ++] = 45; d = - d; } d += Math.pow(10, - precision) / 2; print((long)d); if(precision == 0) return; if(count + precision + 1 > BUF_SIZE) internalFlush(); buf[count ++] = 46; d -= (long)d; for(int i = 0; i < precision; i ++) { d *= 10; buf[count ++] = (byte)((int)d + 48); d -= (int) d; } } public final void print(final String s) { print(s.getBytes()); } public final void print(final Object o) { print(o.toString()); } public final void print(final byte[] a) { if(count + a.length > BUF_SIZE) internalFlush(); System.arraycopy(a, 0, buf, count, a.length); count += a.length; } public final void print(final char[] a) { if(count + a.length > BUF_SIZE) internalFlush(); for(int i = 0; i < a.length; i ++) buf[count + i] = (byte)a[i]; count += a.length; } public final void println() { print('\n'); } public final void println(final char c) { print(c); println(); } public final void println(final boolean b) { print(b); println(); } public final void println(final int x) { print(x); println(); } public final void println(final long x) { print(x); println(); } public final void println(final double d) { print(d); println(); } public final void println(final double d, final int precision) { print(d, precision); println(); } public final void println(final String s) { print(s); println(); } public final void println(final Object o) { print(o); println(); } public final void println(final char[] a) { print(a); println(); } public final void println(final int[] a) { for(int i = 0; i < a.length; i ++) { print(a[i]); print(i == a.length - 1 ? '\n' : ' '); } } public final void println(final long[] a) { for(int i = 0; i < a.length; i ++) { print(a[i]); print(i == a.length - 1 ? '\n' : ' '); } } public final void println(final double[] a) { for(int i = 0; i < a.length; i ++) { print(a[i]); print(i == a.length - 1 ? '\n' : ' '); } } public final void println(final double[] a, final int precision) { for(int i = 0; i < a.length; i ++) { print(a[i], precision); print(i == a.length - 1 ? '\n' : ' '); } } public final void println(final String[] a) { for(int i = 0; i < a.length; i ++) { print(a[i]); print(i == a.length - 1 ? '\n' : ' '); } } public final void println(final Object[] a) { for(int i = 0; i < a.length; i ++) { print(a[i]); print(i == a.length - 1 ? '\n' : ' '); } } private final void internalFlush() { try { out.write(buf, 0, count); count = 0; } catch(IOException e) { e.printStackTrace(); } } public final void flush() { try { out.write(buf, 0, count); out.flush(); count = 0; } catch(IOException e) { e.printStackTrace(); } } public final void close() { try { out.close(); } catch(IOException e) { e.printStackTrace(); } } } abstract class Util implements Runnable { @Override public void run() { solve(); flush(); } abstract public void solve(); public static boolean DEBUG; private static final FastInputStream in = new FastInputStream(System.in); public static final String nline() { return in.nextLine(); } public static final String[] nline(final int n) { final String a[] = new String[n]; for(int i = 0; i < n; i ++) a[i] = nline(); return a; } public static final char nc() { return in.nextChar(); } public static final char[] nc(int n) { final String str = nline(); if(n < 0) n = str.length(); final char a[] = new char[n]; for(int i = 0; i < n; i ++) a[i] = str.charAt(i); return a; } public static final char[][] nc(final int n, final int m) { final char a[][] = new char[n][m]; for(int i = 0; i < n; i ++) a[i] = nc(m); return a; } public static final boolean[] nb(int n, final char t) { final char c[] = nc(-1); if(n < 0) n = c.length; final boolean a[] = new boolean[n]; for(int i = 0; i < n; i ++) a[i] = c[i] == t; return a; } public static final boolean[][] nb(final int n, final int m, final char t) { final boolean a[][] = new boolean[n][]; for(int i = 0; i < n; i ++) a[i] = nb(m, t); return a; } public static final int ni() { return in.nextInt(); } public static final int[] ni(final int n) { final int a[] = new int[n]; for(int i = 0; i < n; i ++) a[i] = ni(); return a; } public static final int[][] ni(final int n, final int m) { final int a[][] = new int[n][]; for(int i = 0; i < n; i ++) a[i] = ni(m); return a; } public static final long nl() { return in.nextLong(); } public static final long[] nl(final int n) { final long a[] = new long[n]; for(int i = 0; i < n; i ++) a[i] = nl(); return a; } public static final long[][] nl(final int n, final int m) { final long a[][] = new long[n][]; for(int i = 0; i < n; i ++) a[i] = nl(m); return a; } public static final double nd() { return in.nextDouble(); } public static final double[] nd(final int n) { final double a[] = new double[n]; for(int i = 0; i < n; i ++) a[i] = nd(); return a; } public static final double[][] nd(final int n, final int m) { final double a[][] = new double[n][]; for(int i = 0; i < n; i ++) a[i] = nd(m); return a; } public static final String ns() { return in.next(); } public static final String[] ns(final int n) { final String a[] = new String[n]; for(int i = 0; i < n; i ++) a[i] = ns(); return a; } public static final String[][] ns(final int n, final int m) { final String a[][] = new String[n][]; for(int i = 0; i < n; i ++) a[i] = ns(m); return a; } private static final FastOutputStream out = new FastOutputStream(System.out); private static final FastOutputStream err = new FastOutputStream(System.err); public static final void prt() { out.print(); } public static final void prt(final char c) { out.print(c); } public static final void prt(final boolean b) { out.print(b); } public static final void prt(final int x) { out.print(x); } public static final void prt(final long x) { out.print(x); } public static final void prt(final double d) { out.print(d); } public static final void prt(final String s) { out.print(s); } public static final void prt(final Object o) { out.print(o); } public static final void prtln() { out.println(); } public static final void prtln(final char c) { out.println(c); } public static final void prtln(final boolean b) { out.println(b); } public static final void prtln(final int x) { out.println(x); } public static final void prtln(final long x) { out.println(x); } public static final void prtln(final double d) { out.println(d); } public static final void prtln(final String s) { out.println(s); } public static final void prtln(final Object o) { out.println(o); } public static final void prtln(final char... a) { out.println(a); } public static final void prtln(final boolean... a) { out.println(booleanToChar(a)); } public static final void prtln(final int... a) { out.println(a); } public static final void prtln(final long... a) { out.println(a); } public static final void prtln(final double... a) { out.println(a); } public static final void prtln(final double[] a, int precision) { out.println(a, precision); } public static final void prtln(final String... a) { out.println(a); } public static final void prtln(final Object[] a) { out.println(a); } public static final void prtlns(final char... a) { for(char ele : a) prtln(ele); } public static final void prtlns(final boolean... a) { for(boolean ele : a) prtln(ele); } public static final void prtlns(final int... a) { for(int ele : a) prtln(ele); } public static final void prtlns(final long... a) { for(long ele : a) prtln(ele); } public static final void prtlns(final double... a) { for(double ele : a) prtln(ele); } public static final void prtlns(final Object[] a) { for(Object ele : a) prtln(ele); } public static final void prtln(final char[][] a) { for(char[] ele : a) prtln(ele); } public static final void prtln(final boolean[][] a) { for(boolean[] ele : a) prtln(ele); } public static final void prtln(final int[][] a) { for(int[] ele : a) prtln(ele); } public static final void prtln(final long[][] a) { for(long[] ele : a) prtln(ele); } public static final void prtln(final double[][] a) { for(double[] ele : a) prtln(ele); } public static final void prtln(final double[][] a, int precision) { for(double[] ele : a) prtln(ele, precision); } public static final void prtln(final String[][] a) { for(String[] ele : a) prtln(ele); } public static final void prtln(final Object[][] a) { for(Object[] ele : a) prtln(ele); } public static final void errprt() { if(DEBUG) err.print(); } public static final void errprt(final char c) { if(DEBUG) err.print(c); } public static final void errprt(final boolean b) { if(DEBUG) err.print(booleanToChar(b)); } public static final void errprt(final int x) { if(DEBUG) if(isINF(x)) err.print('_'); else err.print(x); } public static final void errprt(final long x) { if(DEBUG) if(isINF(x)) err.print('_'); else err.print(x); } public static final void errprt(final double d) { if(DEBUG) err.print(d); } public static final void errprt(final String s) { if(DEBUG) err.print(s); } public static final void errprt(final Object o) { if(DEBUG) err.print(o); } public static final void errprtln() { if(DEBUG) err.println(); } public static final void errprtln(final char c) { if(DEBUG) err.println(c); } public static final void errprtln(final boolean b) { if(DEBUG) err.println(booleanToChar(b)); } public static final void errprtln(final int x) { if(DEBUG) if(isINF(x)) err.println('_'); else err.println(x); } public static final void errprtln(final long x) { if(DEBUG) if(isINF(x)) err.println('_'); else err.println(x); } public static final void errprtln(final double d) { if(DEBUG) err.println(d); } public static final void errprtln(final String s) { if(DEBUG) err.println(s); } public static final void errprtln(final Object o) { if(DEBUG) err.println(o); } public static final void errprtln(final char... a) { if(DEBUG) err.println(a); } public static final void errprtln(final boolean... a) { if(DEBUG) err.println(booleanToChar(a)); } public static final void errprtln(final int... a) { if(DEBUG) { boolean start = false; for(int ele : a) { errprt(ele); if(!start) errprt(' '); start = false; } err.println(); } } public static final void errprtln(final long... a) { if(DEBUG) { boolean start = false; for(long ele : a) { errprt(ele); if(!start) errprt(' '); start = false; } err.println(); } } public static final void errprtln(final double... a) { if(DEBUG) err.println(a); } public static final void errprtln(final double[] a, final int precision) { if(DEBUG) err.println(a, precision); } public static final void errprtln(final String... a) { if(DEBUG) err.println(a); } public static final void errprtln(final Object[] a) { if(DEBUG) err.println(a); } public static final void errprtlns(final char... a) { if(DEBUG) for(char ele : a) errprtln(ele); } public static final void errprtlns(final boolean... a) { if(DEBUG) for(boolean ele : a) errprtln(ele); } public static final void errprtlns(final int... a) { if(DEBUG) for(int ele : a) errprtln(ele); } public static final void errprtlns(final long... a) { if(DEBUG) for(long ele : a) errprtln(ele); } public static final void errprtlns(final double... a) { if(DEBUG) for(double ele : a) errprtln(ele); } public static final void errprtlns(final Object[] a) { if(DEBUG) for(Object ele : a) errprtln(ele); } public static final void errprtln(final char[][] a) { if(DEBUG) for(char[] ele : a) errprtln(ele); } public static final void errprtln(final boolean[][] a) { if(DEBUG) for(boolean[] ele : a) errprtln(ele); } public static final void errprtln(final int[][] a) { if(DEBUG) for(int[] ele : a) errprtln(ele); } public static final void errprtln(final long[][] a) { if(DEBUG) for(long[] ele : a) errprtln(ele); } public static final void errprtln(final double[][] a) { if(DEBUG) for(double[] ele : a) errprtln(ele); } public static final void errprtln(final double[][] a, int precision) { if(DEBUG) for(double[] ele : a) errprtln(ele, precision); } public static final void errprtln(final String[][] a) { if(DEBUG) for(String[] ele : a) errprtln(ele); } public static final void errprtln(final Object[][] a) { if(DEBUG) for(Object[] ele : a) errprtln(ele); } public static final void errprtlns(final Object[][] a) { if(DEBUG) for(Object[] ele : a) { errprtlns(ele); errprtln(); } } public static final void reply(final boolean b) { prtln(b ? "Yes" : "No"); } public static final void REPLY(final boolean b) { prtln(b ? "YES" : "NO"); } public static final void flush() { out.flush(); if(DEBUG) err.flush(); } public static final void inclusiveRangeCheck(final int i, final int max) { inclusiveRangeCheck(i, 0, max); } public static final void inclusiveRangeCheck(final int i, final int min, final int max) { rangeCheck(i, min, max + 1); } public static final void inclusiveRangeCheck(final long i, final long max) { inclusiveRangeCheck(i, 0, max); } public static final void inclusiveRangeCheck(final long i, final long min, final long max) { rangeCheck(i, min, max + 1); } public static final void rangeCheck(final int i, final int max) { rangeCheck(i, 0, max); } public static final void rangeCheck(final int i, final int min, final int max) { if(i < min || i >= max) throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, max)); } public static final void rangeCheck(final long i, final long max) { rangeCheck(i, 0, max); } public static final void rangeCheck(final long i, final long min, final long max) { if(i < min || i >= max) throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, max)); } public static final void nonNegativeCheck(final long x) { nonNegativeCheck(x, "the argument"); } public static final void nonNegativeCheck(final long x, final String attribute) { if(x < 0) throw new IllegalArgumentException(String.format("%s %d is negative", attribute, x)); } public static final void positiveCheck(final long x) { positiveCheck(x, "the argument"); } public static final void positiveCheck(final long x, final String attribute) { if(x <= 0) throw new IllegalArgumentException(String.format("%s %d is negative", attribute, x)); } public static final long INF = (long)4e18; public static final boolean isPlusINF(final long x) { return x > INF / 10; } public static final boolean isMinusINF(final long x) { return isPlusINF(- x); } public static final boolean isINF(final long x) { return isPlusINF(x) || isMinusINF(x); } public static final int I_INF = (int)1e9 + 1000; public static final boolean isPlusINF(final int x) { return x > I_INF / 10; } public static final boolean isMinusINF(final int x) { return isPlusINF(- x); } public static final boolean isINF(final int x) { return isPlusINF(x) || isMinusINF(x); } public static final char booleanToChar(final boolean b) { return b ? '#' : '.'; } public static final char[] booleanToChar(final boolean... a) { final char c[] = new char[a.length]; for(int i = 0; i < a.length; i ++) c[i] = booleanToChar(a[i]); return c; } public static final long mod(long x, final long mod) { if(0 <= x && x < mod) return x; if(- mod <= x && x < 0) return x + mod; return (x %= mod) < 0 ? x + mod : x; } public static final long pow(long x, long y, final long mod) { nonNegativeCheck(y); x = mod(x, mod); long ans = 1; for(; y > 0; y >>= 1) { if((y & 1) != 0) ans = mod(ans * x, mod); x = mod(x * x, mod); } return ans; } } public class Main extends Util { public static void main(final String[] args) { DEBUG = args.length > 0 && args[0].equals("-DEBUG"); Thread.setDefaultUncaughtExceptionHandler((t, e) -> { flush(); e.printStackTrace(); System.exit(1); }); new Thread(null, new Main(), "", 1 << 31).start(); } public void solve() { Mod md = new ArbitraryMod(nl()); int n = ni() - 1; long ans = nl(); long a[] = nl(n); for(long ele : a) { switch(nc()) { case '+': ans = md.add(ans, ele); break; case '-': ans = md.sub(ans, ele); break; case '*': ans = md.mul(ans, ele); break; case '/': ans = md.div(ans, ele); break; } } prtln(ans); } } abstract class Mod { public final long MOD; public Mod(long mod) { MOD = mod; } public abstract long mod(long x); public final long[] mod(final long[] a) { for(int i = 0; i < a.length; i ++) a[i] = mod(a[i]); return a; } public final long[][] mod(final long[][] a) { for(int i = 0; i < a.length; i ++) mod(a[i]); return a; } public final long[][][] mod(final long[][][] a) { for(int i = 0; i < a.length; i ++) mod(a[i]); return a; } public long add(long x, final long y) { return (x += y) >= MOD * 2 || x < 0 ? mod(x) : x >= MOD ? x - MOD : x; } public final long sum(final long... x) { long sum = 0; for(long ele : x) sum = add(sum, ele); return sum; } public long sub(long x, final long y) { return (x -= y) < - MOD || x >= MOD ? mod(x) : x < 0 ? x + MOD : x; } public final long pow(long x, long y) { Util.nonNegativeCheck(y); x = mod(x); long ans = 1; for(; y > 0; y >>= 1) { if((y & 1) != 0) ans = mul(ans, x); x = mul(x, x); } return ans; } public abstract long mul(long x, long y); public final long mul(final long... x) { long ans = 1; for(long ele : x) ans = mul(ans, ele); return ans; } public final long div(final long x, final long y) { return mul(x, inv(y)); } public final long[] pows(long x, final int n) { x = mod(x); long pow[] = new long[n + 1]; pow[0] = 1; for(int i = 0; i < n; i ++) pow[i + 1] = mul(pow[i], x); return pow; } public final long fact(final int n) { Util.nonNegativeCheck(n); prepareFact(); if(n < MAX_FACT1) return fact[n]; else { long ans = fact[MAX_FACT1 - 1]; for(int i = MAX_FACT1; i <= n; i ++) ans = mul(ans, i); return ans; } } public final long invFact(final int n) { Util.nonNegativeCheck(n); prepareFact(); if(n < MAX_FACT1) return invFact[n]; else return inv(fact(n)); } private static final int MAX_INV_SIZE = 100_100; private final Map<Long, Long> invMap = new HashMap<>(); public final long inv(long x) { x = mod(x); if(invMap.containsKey(x)) return invMap.get(x); if(invMap.size() >= MAX_INV_SIZE) return calInv(x); invMap.put(x, calInv(x)); return invMap.get(x); } private final long calInv(final long x) { // O(logM) long s0 = MOD, s1 = 0; long t0 = mod(x), t1 = 1; while(t0 > 0) { final long tmp = s0 / t0; final long u0 = s0 - t0 * tmp; final long u1 = s1 - t1 * tmp; s0 = t0; s1 = t1; t0 = u0; t1 = u1; } if(s0 != 1) throw new ArithmeticException("/ by zero"); if(s1 < 0) s1 += MOD; return s1; } public final long[] invs(final int n) { // O(N) Util.positiveCheck(n); long inv[] = new long[n + 1]; inv[1] = 1; for(int i = 2; i <= n; i ++) inv[i] = mul(inv[(int)(MOD % i)], (MOD - MOD / i)); return inv; } private long g; public final long primitiveRoot() { // O(1) or O(M^(1/2)) if(MOD == 2) return 1; if(MOD == 167772161) return 3; if(MOD == 469762049) return 3; if(MOD == 754974721) return 11; if(MOD == 998244353) return 3; if(g != 0) return g; // PairLL factor[] = factor(MOD - 1); // outer: for(g = 2; ; g ++) { // for(PairLL p : factor) if(pow(g, (MOD - 1) / p.a) == 1) continue outer; // return g; // } return 0; } private static final int MAX_FACT1 = 5_000_100; private static final int MAX_FACT2 = 500_100; private static final int MAX_FACT_MAP_SIZE = 100; private long fact[]; private long invFact[]; private boolean isFactPrepared = false; private final Map<Long, long[]> factMap = new HashMap<>(); private final void prepareFact() { if(isFactPrepared) return; fact = new long[MAX_FACT1]; invFact = new long[MAX_FACT1]; fact[0] = 1; int maxIndex = Math.min(MAX_FACT1, (int)MOD); for(int i = 1; i < maxIndex; i ++) fact[i] = mul(fact[i - 1], i); invFact[maxIndex - 1] = inv(fact[maxIndex - 1]); for(int i = maxIndex - 1; i > 0; i --) invFact[i - 1] = mul(invFact[i], i); isFactPrepared = true; } public final long P(final long n, final long r) { if(!isFactPrepared) prepareFact(); if(n < 0 || r < 0 || n < r) return 0; if(n < MAX_FACT1 && n < MOD) return mul(fact[(int)n], invFact[(int)(n - r)]); if(!factMap.containsKey(n)) { long largeFact[] = new long[MAX_FACT2]; factMap.put(n, largeFact); Arrays.fill(largeFact, -1); largeFact[0] = 1; } long largeFact[] = factMap.get(n); if(r >= MAX_FACT2) { long ans = 1; for(long i = n - r + 1; i <= n; i ++) ans = mul(ans, i); return ans; }else { int i = (int)r; while(largeFact[i] < 0) i --; for(; i < r; i ++) largeFact[i + 1] = mul(largeFact[i], n - i); if(factMap.size() > MAX_FACT_MAP_SIZE) factMap.remove(n); return largeFact[(int)r]; } } public final long C(long n, long r) { if(!isFactPrepared) prepareFact(); if(n < 0) return mod(C(- n + r - 1, - n - 1) * ((r & 1) == 0 ? 1 : -1)); if(r < 0 || n < r) return 0; r = Math.min(r, n - r); if(n < MOD) return mul(P(n, r), r < MAX_FACT1 ? invFact[(int)r] : inv(fact((int)r))); long ans = 1; while(n > 0) { final long n2 = n / MOD; final long r2 = r / MOD; ans = mul(ans, C(n - n2 * MOD, r - r2 * MOD)); n = n2; r = r2; } return ans; } public final long H(final long n, final long r) { return C(n - 1 + r, r); } public final long sqrt(long x) { x = mod(x); long p = (MOD - 1) >> 1; if(pow(x, p) != 1) return -1; long q = MOD - 1; int m = 1; while(((q >>= 1) & 1) == 0) m ++; long z = 1; while(pow(z, p) == 1) z = (long)Math.floor(Math.random() * (MOD - 1)) + 1; long c = pow(z, q); long t = pow(x, q); long r = pow(x, (q + 1) >> 1); if(t == 0) return 0; m -= 2; while(t != 1) { long pows[] = new long[m + 1]; pows[0] = t; for(int i = 0; i < m; i ++) pows[i + 1] = mul(pows[i], pows[i]); while(pows[m --] == 1) c = mul(c, c); r = mul(r, c); c = mul(c, c); t = mul(t, c); } return r; } } final class ArbitraryMod extends Mod { private static final long MASK = 0xffff_ffffl; private final long MH; private final long ML; public ArbitraryMod(long mod) { super(mod); long a = (1l << 32) / MOD; long b = (1l << 32) % MOD; long m = a * a * MOD + 2 * a * b + (b * b) / MOD; MH = m >>> 32; ML = m & MASK; } private final long reduce(long x) { if(MOD == 1) return 0; if(x < 0) return (x = reduce(- x)) == 0 ? 0 : MOD - 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 x < MOD ? x : x - MOD; } @Override public long mod(long x) { if(0 <= x && x < MOD) return x; if(- MOD <= x && x < 0) return x + MOD; return reduce(x); } @Override public long mul(long x, long y) { if(x >= 0 && x < MOD && y >= 0 && y < MOD) return reduce(x * y); x = mod(x); y = mod(y); return reduce(x * y); } }