結果
| 問題 |
No.1186 長方形の敷き詰め
|
| コンテスト | |
| ユーザー |
 shun_skycrew
|
| 提出日時 | 2022-09-17 17:39:45 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 215 ms / 2,000 ms |
| コード長 | 29,108 bytes |
| コンパイル時間 | 3,963 ms |
| コンパイル使用メモリ | 94,120 KB |
| 実行使用メモリ | 120,820 KB |
| 最終ジャッジ日時 | 2024-12-22 00:54:36 |
| 合計ジャッジ時間 | 9,279 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
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 = Mod998.md;
int n = ni();
int m = ni();
if(n == 1) prtln(1);
else {
long ans = 0;
for(int x = 0; x <= m / n; x ++) {
ans = md.add(ans, md.H(x + 1, m - x * n));
}
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 Mod998 extends Mod {
public static final Mod998 md = new Mod998();
public static final long MOD = 998_244_353;
private Mod998() { super(MOD); }
@Override
public final long mod(long x) {
if(0 <= x && x < MOD) return x;
if(- MOD <= x && x < 0) return x + MOD;
return (x %= MOD) < 0 ? x + MOD : x;
}
@Override
public final long mul(long x, long y) {
if(x >= 0 && x < MOD && y >= 0 && y < MOD) return (x * y) % MOD;
x = mod(x);
y = mod(y);
return (x * y) % MOD;
}
}