結果
問題 |
No.3242 Count 8 Included Numbers (Hard)
|
ユーザー |
|
提出日時 | 2025-08-23 07:30:48 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 29,864 bytes |
コンパイル時間 | 6,517 ms |
コンパイル使用メモリ | 95,944 KB |
実行使用メモリ | 63,620 KB |
最終ジャッジ日時 | 2025-08-23 07:31:02 |
合計ジャッジ時間 | 11,129 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 1 TLE * 1 -- * 18 |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintStream; import java.io.PrintWriter; import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.NoSuchElementException; import java.util.Random; import java.util.stream.IntStream; import java.util.stream.LongStream; class Polynomial { static long mod = 998244353; public long[] f; static long[][] bitreversedRoots = new long[30][]; static long[][] bitreversedInvRoots = new long[30][]; public Polynomial(long[] v) { if (v != null) f = Arrays.copyOf(v, v.length); } public static Polynomial of(long[] v) { return new Polynomial(v); } static long ADD(long a,long b) { return a+b>=mod?a+b-mod:a+b; } static long SUB(long a,long b) { return ADD(a,mod-b); } static void prepareRoots(int n) { int sz = Integer.numberOfTrailingZeros(n); if (bitreversedRoots[sz] != null) return; long g = 3; long root = MathUtils.modPow(g, (mod - 1) / n, mod); long iroot = MathUtils.modInv(root, mod); bitreversedRoots[sz] = new long[n]; bitreversedInvRoots[sz] = new long[n]; for (int n_ = n / 2; n_ >= 1; n_ /= 2, root = root * root % mod, iroot = iroot * iroot % mod) { long w = 1; long iw = 1; for(int j=0;j<n_;++j) { bitreversedRoots[sz][n_+j] = w; bitreversedInvRoots[sz][n_+j] = iw; w = w * root % mod; iw = iw * iroot % mod; } int cur=0; for(int j=0;j<n_;++j) { if(cur<j) { ArrayUtils.swap(n_+cur,n_+j,bitreversedRoots[sz]); ArrayUtils.swap(n_+cur,n_+j,bitreversedInvRoots[sz]); } for (int k=n_/2;k>(cur^=k);k/=2) ; } } } public static void fft(long[] a, long g) { int n=a.length; { int cur=0; for (int i=0;i<n;++i) { if (cur<i) { a[i]^=a[cur];a[cur]^=a[i];a[i]^=a[cur]; } for (int k=n/2;k>(cur^=k);k/=2) ; } } for (int s=1;s<=n/2;s*=2) { long mul=MathUtils.modPow(g,n/(2*s),mod); for (int i=0;i<n;i+=2*s) { long x=1; for (int j=0;j<s;++j) { long A=a[i+j]; long B=a[i+j+s]*x%mod; a[i+j]=ADD(A,B); a[i+j+s]=SUB(A,B); x=x*mul%mod; } } } } static void ifft(long[] a, long g) { int n=a.length; { int cur=0; for (int i=0;i<n;++i) { if (cur<i) { a[i]^=a[cur];a[cur]^=a[i];a[i]^=a[cur]; } for (int k=n/2;k>(cur^=k);k/=2) ; } } long invN = MathUtils.modInv(a.length, mod); for (int s=1;s<=n/2;s*=2) { long mul=MathUtils.modPow(g,n/(2*s),mod); for (int i=0;i<n;i+=2*s) { long x=(s==n/2?invN:1); for (int j=0;j<s;++j) { long A=a[i+j]; long B=a[i+j+s]*x%mod; if(s==n/2)A=A*invN%mod; a[i+j]=ADD(A,B); a[i+j+s]=SUB(A,B); x=x*mul%mod; } } } } /** * Scott, Michael. "A note on the implementation of the number theoretic transform." IMA International Conference on Cryptography and Coding. Cham: Springer International Publishing, 2017. * @param a */ public static void fftTobitReversed(long[] a) { int n=a.length; int sz=Integer.numberOfTrailingZeros(a.length); if (bitreversedRoots[sz] == null) prepareRoots(a.length); for(int m = 1, t = n/2; m <= n/2; m *= 2, t /= 2) { for(int i = 0, k = 0; i<m; ++i, k += 2*t) { long S=bitreversedRoots[sz][m+i]; for(int j=k;j<k+t;++j) { long u=a[j]; long v=a[j+t]*S%mod; a[j]=ADD(u,v); a[j+t]=SUB(u,v); } } } } /** * Scott, Michael. "A note on the implementation of the number theoretic transform." IMA International Conference on Cryptography and Coding. Cham: Springer International Publishing, 2017. * @param a */ public static void ifftFromBitreversed(long[] a) { long invN = MathUtils.modInv(a.length, mod); int n=a.length; int sz = Integer.numberOfTrailingZeros(n); if (bitreversedInvRoots[sz] == null) prepareRoots(a.length); for(int m = n/2, t = 1; m >= 1; m /= 2, t *= 2) { for(int i = 0, k = 0; i<m; ++i, k += 2*t) { long S=bitreversedInvRoots[sz][m+i]; if (m == 1) S=S*invN%mod; for(int j=k;j<k+t;++j) { long u=a[j]; long v=a[j+t]; if(m == 1) a[j] = (u + v) * invN % mod; else a[j]=ADD(u,v); a[j+t]=(u+mod-v)*S%mod; } } } } public static long[] add(long[] a,long[] b) { long[] ret=new long[Math.max(a.length, b.length)]; for (int i=0;i<ret.length;++i) ret[i]=ADD(i<a.length?a[i]:0,i<b.length?b[i]:0); return ret; } public static long[] subtract(long[] a,long[] b) { long[] ret=new long[Math.max(a.length, b.length)]; for (int i=0;i<ret.length;++i) ret[i]=ADD(i<a.length?a[i]:0,i<b.length?(mod-b[i]):0); return ret; } static long[] mulFFT(long[] a,long[] b) { int n=1; while (n<a.length+b.length-1) n*=2; a=Arrays.copyOf(a, n); b=Arrays.copyOf(b, n); prepareRoots(n); fftTobitReversed(a); fftTobitReversed(b); for (int i = 0; i < a.length; ++i) a[i] = a[i] * b[i] % mod; ifftFromBitreversed(a); return a; } public static long[] mul(long[] a, long[] b) { if (a.length + b.length - 1 <= 512) { long[] ret=new long[a.length+b.length-1]; for(int i=0;i<a.length;++i) { for(int j=0;j<b.length;++j) { ret[i+j]+=a[i]*b[j]; ret[i+j]%=mod; } } return ret; } else { return mulFFT(a, b); } } public static long[] squared(long[] a) { if (a.length <= 1024) { long[] ret=new long[2 * a.length+a.length-1]; for(int i=0;i<a.length;++i) { for(int j=i + 1;j<a.length;++j) { ret[i+j]+=2*a[i]*a[j]; ret[i+j]%=mod; } } for (int i = 0; i < a.length; ++i) { ret[2 * i] += a[i] * a[i]; ret[2 * i] %= mod; } return ret; } else { int n=1; while (n<a.length+a.length-1) n*=2; a=Arrays.copyOf(a, n); prepareRoots(n); fftTobitReversed(a); for (int i = 0; i < a.length; ++i) a[i] = a[i] * a[i] % mod; ifftFromBitreversed(a); return a; } } public static long[] sqrt(long[] a) { long[] ret=new long[a.length]; long b=MathUtils.modKthRoot(a[0],2,mod); ret=mul(a,MathUtils.modInv(a[0],mod)); ret=log(ret); ret=mul(ret,MathUtils.modInv(2,mod)); ret=exp(ret); ret=mul(ret,b); return ret; } public static long[] pow(long[] a,long m) { int len = a.length; if(m==0) { long[] ret=new long[a.length]; ret[0]=1; return ret; } else if (m==1) { return a; } else if (m == 2) { return squared(a); } int s=0; while (s<a.length && a[s]==0) ++s; if (s==a.length) return a; if (s != 0) a=Arrays.copyOfRange(a, s, a.length); long b=MathUtils.modInv(a[0], mod); for (int i=0;i<a.length;++i) a[i]=b*a[i]%mod; a=log(a); for (int i=0;i<a.length;++i) a[i]=m%mod*a[i]%mod; a=exp(a); b=MathUtils.modPow(MathUtils.modInv(b, mod),m%(mod-1), mod); for (int i=0;i<a.length;++i) a[i]=b*a[i]%mod; long[]ret=new long[len]; if(s <= (len - 1) / m) { for(long i = s * m; i<len && i - s * m < a.length;++i) { ret[(int) i] = a[(int) (i - s * m)]; } } return ret; } static long[] log(long[] a) { return integrate(resize(mul(differentiate(a), inv(a)),a.length)); } /** * A simple and fast algorithm for computing exponentials of power series. Alin Bostan * @param a * @return */ public static long[] exp(long[] a) { long[] exp=new long[1]; long[] iexp=new long[1]; exp[0]=1; iexp[0]=1; long[] differeniatedA = differentiate(a); long[] differentiatedExp = new long[2 * a.length]; for (int len=1;len<a.length;len*=2) { long[] expFFT = resize(exp, 2 * len); long[] iexpFFT = resize(iexp, 2 * len); fftTobitReversed(expFFT); fftTobitReversed(iexpFFT); long[] x = new long[2 * len]; for (int i = 0; i < 2 * len; ++i) { x[i] = iexpFFT[i] * iexpFFT[i] % mod * expFFT[i] % mod; } ifftFromBitreversed(x); if (len !=1 ) iexp = resize(add(iexp, subtract(iexp, x)), len); long[] q = resize(differeniatedA, len); long[] qFFT = resize(q, len); long[] expFFT2 = resize(expFFT, len); fftTobitReversed(qFFT); for (int i = 0; i < q.length; ++i) { qFFT[i] = qFFT[i] * expFFT2[i] % mod; } ifftFromBitreversed(qFFT); long[] s = new long[len]; for (int i = 0; i < len; ++i) { s[i] = (exp[i] * i + mod - (i == 0 ? qFFT[len - 1] : qFFT[i - 1])) % mod; } long[] t = resize(mul(s, iexp), len); t = multiplyByX(t, len - 1); q = add(q, t); q = resize(q, 2*len); long[] u=divideByX(subtract(resize(a, 2*len), integrate(q)), len); u = resize(u, 2*len); fftTobitReversed(u); for (int i = 0; i < u.length; ++i) u[i] = u[i] * expFFT[i] % mod; ifftFromBitreversed(u); exp = add(exp, multiplyByX(resize(u,len), len)); if (2 * len < a.length) { for (int i = len; i < 2 * len; ++i) { differentiatedExp[i - 1] = i * exp[i] % mod; } } } exp = resize(exp, a.length); return exp; } static long[] exp2(long[] a) { long[] exp=new long[a.length]; exp[0]=1; for (int len=1;len<a.length;len*=2) { long[] tmp=subtract(resize(a,2*len),log(resize(exp,2*len))); ++tmp[0]; exp=resize(mul(exp,tmp),2*len); } return exp; } static long[] differentiate(long[] a) { long[] ret=new long[a.length]; for (int i=1;i<a.length;++i) ret[i-1]=i*a[i]%mod; return ret; } static long[] integrate(long[] a) { long[] ret=new long[a.length]; for (int i=0;i+1<a.length;++i) ret[i+1]=MathUtils.modInv(i+1,mod)*a[i]%mod; return ret; } public static long[] inv(long[] a) { long[] g=new long[1]; g[0]=MathUtils.modInv(a[0],mod); for (int len=1;len<a.length;len*=2) { long[] fftG=Arrays.copyOf(g, len * 4); long[] fftA=new long[4 * len]; System.arraycopy(a, 0, fftA, 0, Math.min(2 * len, a.length)); prepareRoots(4*len); fftTobitReversed(fftG); fftTobitReversed(fftA); for (int i = 0; i < fftG.length; ++i) { fftG[i] = fftG[i] * fftG[i] % mod * fftA[i] % mod; } ifftFromBitreversed(fftG); for (int i = 0; i < len; ++i) { fftG[i] = g[i]; } for (int i = len; i < 2 * len; ++i) { if (fftG[i]!=0) fftG[i] = mod - fftG[i]; } g=resize(fftG,2*len); } return g; } public static long[] mul(long[] a,long b) { long[] ret=new long[a.length]; for (int i=0;i<a.length;++i) ret[i]=a[i]*b%mod; return ret; } static long[] resize(long[] a,int len) { return Arrays.copyOf(a, len); } public Polynomial mul(long a) { return new Polynomial(mul(f, a)); } public Polynomial mul(Polynomial poly) { return new Polynomial(mul(f, poly.f)); } public Polynomial sqrt() { Polynomial poly = new Polynomial(null); poly.f = exp(f); return poly; } public Polynomial inv() { Polynomial poly = new Polynomial(null); poly.f = inv(f); return poly; } public Polynomial subtract(Polynomial p) { Polynomial poly = new Polynomial(null); poly.f = subtract(f, p.f); return poly; } public Polynomial add(Polynomial p) { Polynomial poly = new Polynomial(null); poly.f = add(f, p.f); return poly; } /** * f^src/(1-f) を返す */ public Polynomial geometricSeries(int src) { return new Polynomial(mul(pow(f, src), inv(subtract(new long[] {1}, f)))); } public Polynomial resize(int n) { return new Polynomial(Arrays.copyOf(f, n)); } /** * f / x^n を返す。ただし、f は x^n を因数に持つとする */ public static long[] divideByX(long[] f, int repeat) { return Arrays.copyOfRange(f, repeat, f.length); } public static long[] multiplyByX(long[] f, int repeat) { long[] ret = new long[f.length + repeat]; for (int i = 0; i < f.length; ++i) ret[repeat + i] = f[i]; return ret; } public Polynomial multiplyByX(int repeat) { Polynomial poly = new Polynomial(null); poly.f = multiplyByX(f, repeat); return poly; } public Polynomial pow(int n) { return new Polynomial(pow(f, n)); } public static Polynomial motzkin(int n) { ModInt mi = new ModInt(mod); Polynomial poly = new Polynomial(new long[n]); poly.f[0] = 1; poly.f[1] = 1; for (int i = 2; i < n; ++i) { poly.f[i] = ((2 * i + 1)*poly.f[i - 1]+(3*i-3)*poly.f[i-2]) % mod*mi.inv(i + 2); poly.f[i] = (poly.f[i] % mod + mod)%mod; } return poly; } public static Polynomial centralTrinomials(int n) { ModInt mi = new ModInt(mod); Polynomial poly = new Polynomial(new long[n]); poly.f[0] = 1; poly.f[1] = 1; for (int i = 2; i < n; ++i) { poly.f[i] = 2*poly.f[i - 1]+3*poly.f[i-2]-(poly.f[i-1]+3*poly.f[i-2])*mi.inv(i); poly.f[i] = (poly.f[i] % mod + mod)%mod; } return poly; } static void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));} } class ModInt { long mod; long[] fac = new long[0]; long[] ifac = new long[0]; long[] inv = new long[0]; long[] fib = new long[0]; public ModInt(long mod) { this.mod = mod; } void expand(int n) { fac = new long[n]; ifac = new long[n]; inv = new long[n]; Arrays.fill(fac, 1); Arrays.fill(ifac, 1); Arrays.fill(inv, 1); for (int i = 2; i < n; ++i) { fac[i] = i * fac[i - 1] % mod; inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod; ifac[i] = inv[i] * ifac[i - 1] % mod; } } public long fac(int n) { if (fac.length <= n) { expand(Math.max(2 * fac.length, n + 1)); } return fac[n]; } public long ifac(int n) { if (ifac.length <= n) { expand(Math.max(2 * ifac.length, n + 1)); } return ifac[n]; } public long inv(int n) { if (inv.length <= n) { expand(Math.max(2 * inv.length, n + 1)); } return inv[n]; } public long comb(int n, int k) { if (k < 0 || n - k < 0) return 0; return fac(n) * ifac(k) % mod * ifac(n - k) % mod; } public long fib(int n) { if (fib.length <= n) { fib = new long[2 * Integer.highestOneBit(n)]; fib[0] = 1; fib[1] = 1; for (int i = 2; i < fib.length; ++i) { fib[i] = (fib[i - 1] + fib[i - 2]) % mod; } } return fib[n]; } public long mul(Long...a) { long ret = 1; for (long v : a) ret = ret * v % mod; return ret; } public long pow(long a, long n) { return MathUtils.modPow(a, n, mod); } } class FastScanner { private static FastScanner instance = null; private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private FastScanner() {} // 外部から new できないようにする public static FastScanner getInstance() { if (instance == null) { instance = new FastScanner(); } return instance; } private boolean hasNextByte() { if (ptr < buflen) return true; ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } return buflen > 0; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } while (b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n; } public int nextInt() { return (int) nextLong(); } public long[] nextLongs(int n) { long[] a = new long[n]; for (int i = 0; i < n; ++i) { a[i] = nextLong(); } return a; } public int[] nextInts(int n) { int[] a = new int[n]; for (int i = 0; i < n; ++i) { a[i] = nextInt(); } return a; } } class ArrayUtils { public static void swap(int i, int j, int[]A){ if(i == j) return; int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } public static void swap(int i, int j, long[]A){ if(i == j) return; long tmp = A[i]; A[i] = A[j]; A[j] = tmp; } /** * swap A[i] and A[j] */ public static void swap(int i, int j, long[][]A){ if(i == j) return; long[] tmp = Arrays.copyOf(A[i], A[i].length); A[i] = A[j]; A[j] = tmp; } /** * {1,2,..,n} から {start, start+1, .., end - 1} へのランダムな写像 * @param start (inclusive) * @param end (exclusive) * @param length * @return */ public static int[] randomIntArray(int start, int end, int length) { int[] ret = new int[length]; Random rnd=new Random(); Arrays.setAll(ret, i -> rnd.nextInt(start, end)); return ret; } /** * {1,2,..,n} から {start, start+1, .., end - 1} へのランダムな写像 * @param start (inclusive) * @param end (exclusive) * @param length * @return */ public static long[] randomLongArray(long start, long end, int length) { long[] ret = new long[length]; Random rnd=new Random(); Arrays.setAll(ret, i -> rnd.nextLong(start, end)); return ret; } /** * {start, start+1, .., end - 1}^n における辞書順の次の要素にAを変更する。 * @param start (inclusive) * @param end (exclusive) * @param length * @return */ public static boolean nextArray(int[] A, int start, int end) { int t=A.length-1; while(t >= 0 && A[t]==end-1)--t; if(t == -1)return false; A[t]++; for(int i=t+1;i<A.length;++i)A[i]=start; return true; } public static int[] range(int startInclusive, int endExclusive) { return IntStream.range(startInclusive, endExclusive).toArray(); } public static void fill(long[][] a, long v) { for(int i=0;i<a.length;++i) { for(int j=0;j<a[i].length;++j) { a[i][j]=v; } } } public static void fill(int[][] a, int v) { for(int i=0;i<a.length;++i) { for(int j=0;j<a[i].length;++j) { a[i][j]=v; } } } public static void fill(char[][] a, char v) { for(int i=0;i<a.length;++i) { for(int j=0;j<a[i].length;++j) { a[i][j]=v; } } } public static void fill(long[][][] a, long v) { for(int i=0;i<a.length;++i) { for(int j=0;j<a[i].length;++j) { for(int k=0;k<a[i][j].length;++k) { a[i][j][k]=v; } } } } public static void fill(int[][][] a, int v) { for(int i=0;i<a.length;++i) { for(int j=0;j<a[i].length;++j) { for(int k=0;k<a[i][j].length;++k) { a[i][j][k]=v; } } } } public static void reverse(int[] a) { int s = 0; int t = a.length - 1; while (s < t) { swap(s, t, a); ++s;--t; } } public static void reverse(long[] a) { int s = 0; int t = a.length - 1; while (s < t) { swap(s, t, a); ++s;--t; } } /** * a[i] <= key となる最大の i を返す。aはソートされているとする。 * @param a * @param key * @return */ public static int floor(int[] a, int key) { int ok = -1; int ng = a.length; while(ng - ok > 1) { int m = (ok + ng) / 2; if (a[m] <= key) ok=m; else ng = m; } return ok; } /** * key <= a[i] となる最小の i を返す。aはソートされているとする。 * @param a * @param key * @return */ public static int ceil(int[] a, int key) { int ok = a.length; int ng = -1; while(ok - ng > 1) { int m = (ok + ng) / 2; if (a[m] >= key) ok=m; else ng = m; } return ok; } /** * a[i] <= key となる最大の i を返す。 * @param a * @param key * @return */ public static int floor(long[] a, long key) { int ok = -1; int ng = a.length; while(ng - ok > 1) { int m = (ok + ng) / 2; if (a[m] <= key) ok=m; else ng = m; } return ok; } /** * key <= a[i] となる最小の i を返す。 * @param a * @param key * @return */ public static int ceil(long[] a, long key) { int ok = a.length; int ng = -1; while(ok - ng > 1) { int m = (ok + ng) / 2; if (a[m] >= key) ok=m; else ng = m; } return ok; } /** * 配列を連結する * @param a * @return */ public static long[] concat(long[]... a) { int len = 0; for (int i = 0; i < a.length; ++i) { len += a[i].length; } int src = 0; long[] ret = new long[len]; for (int i = 0; i < a.length; ++i) { for (int j = 0; j < a[i].length; ++j) { ret[src + j] = a[i][j]; } src += a[i].length; } return ret; } public static int[] concat(int[]... a) { int len = 0; for (int i = 0; i < a.length; ++i) { len += a[i].length; } int src = 0; int[] ret = new int[len]; for (int i = 0; i < a.length; ++i) { for (int j = 0; j < a[i].length; ++j) { ret[src + j] = a[i][j]; } src += a[i].length; } return ret; } public static boolean equals(long[] a, long[] b) { if (a.length != b.length) return false; for (int i = 0; i < a.length; ++i) if (a[i] != b[i]) return false; return true; } /** * a.length が2冪を仮定 * @param a */ public static void bitReveseOrder(long[]a) { int n = a.length; int cur=0; for (int i=0;i<n;++i) { if (cur<i) { swap(i, cur, a); } for (int k=n/2;k>(cur^=k);k/=2) ; } } /** * a.length が2冪を仮定 * @param a */ public static void bitReveseOrder(int[]a) { int n = a.length; int cur=0; for (int i=0;i<n;++i) { if (cur<i) { swap(i, cur, a); } for (int k=n/2;k>(cur^=k);k/=2) ; } } /** * b[i] = a[1] + a[2] + .. + a[i] * @param a * @param mod * @return */ public static long[] modPrefixSum(long[] a, long mod) { long[] b = new long[a.length]; for (int i = 0; i < b.length; ++i) { b[i] = ((i == 0 ? 0 : b[i - 1]) + a[i]) % mod; } return b; } /** * b[i] = a[1] + a[2] + .. + a[i] * @param a * @param mod * @return */ public static long[] prefixSum(long[] a) { long[] b = new long[a.length]; for (int i = 0; i < b.length; ++i) { b[i] = (i == 0 ? 0 : b[i - 1]) + a[i]; } return b; } public static long[][] copy(long[][] a) { long[][] b = new long[a.length][]; Arrays.setAll(b, i -> Arrays.copyOf(a[i], a[i].length)); return b; } public char[][] rightRotateGrid(char[][] a) { char[][] b = new char[a[0].length][a.length]; for (int i = 0; i < a.length; ++i) { for (int j = 0; j < a[i].length; ++j) { b[j][a.length-1-i]=a[i][j]; } } return b; } } class MyPrintWriter extends PrintWriter { public MyPrintWriter(PrintStream out) { super(out); } public void print(long[] a) { print(a, " "); } public void print(int[] a) { print(a, " "); } public void print(int[] a, String separator) { for (int i = 0; i < a.length; ++i) { super.print(a[i]+(i==a.length-1?"\n":separator)); } } public void print(long[] a, String separator) { for (int i = 0; i < a.length; ++i) { super.print(a[i]+(i==a.length-1?"\n":separator)); } } public void printlnYesNo(boolean flag) { println(flag?"Yes":"No"); } } class MathUtils { /** * ニュートン法を用いて、sqrtを計算する。 * x-f(x)/f'(x)=x-(x**2-n)/2x=x-x/2+n/(2x)=(x*x+n)/(2x) */ public static int sqrt(long a) { if(a==0)return 0; long ret=a; while(true) { long nret=(ret+a/ret)/2; if(nret>=ret)break; ret=nret; } return (int)ret; } public static long ceil(long a, long b) { return (a + b - 1) / b; } public static long gcd(long a, long b) { if (a == 0) return b; return gcd(b % a, a); } public static long modPow(long a, long n, long mod) { if (n == 0) return 1; return modPow(a * a % mod, n / 2, mod) * (n % 2 == 1 ? a : 1) % mod; } public static long pow(long a, long n) { if (n == 0) return 1; return pow(a * a, n / 2) * (n % 2 == 1 ? a : 1); } public static long modKthRoot(long a, long k, long mod) { if (k == 0) return a == 1 ? 1 : -1; if (k >0 && a == 0) return 0; long g = gcd(k, mod - 1); if (modPow(a, (mod - 1) / g, mod) != 1) return -1; a = modPow(a, modInv(k / g, (mod - 1) / g), mod); for (long div = 2; div * div <= g; ++div) { int sz = 0; while (g % div == 0) { g /= div; ++sz; } if (sz > 0) { long b = peth_root(a, div, sz, mod); a = b; } } if (g > 1) a = peth_root(a, g, 1, mod); return a; } private static long peth_root(long a, long p, int e, long mod) { long q = mod - 1; int s = 0; while (q % p == 0) { q /= p; ++s; } long pe = modPow(p, e, mod); long ans = modPow(a, ((pe - 1) * modInv(q, pe) % pe * q + 1) / pe, mod); long c = 2; while (modPow(c, (mod - 1) / p, mod) == 1) ++c; c = modPow(c, q, mod); HashMap<Long, Integer> map = new HashMap<>(); long add = 1; int v = (int) Math.sqrt(p) + 1; long mul = modPow(c, v * modPow(p, s - 1, mod - 1), mod); for (int i = 0; i <= v; ++i) { map.put(add, i); add = add * mul % mod; } mul = modInv(modPow(c, modPow(p, s - 1, mod - 1), mod), mod); out: for (int i = e; i < s; ++i) { long err = modInv(modPow(ans, pe, mod), mod) * a % mod; long target = modPow(err, modPow(p, s - 1 - i, mod - 1), mod); for (int j = 0; j <= v; ++j) { if (map.containsKey(target % mod)) { int x = map.get(target % mod); ans = ans * modPow(c, (j + v * x) * modPow(p, i - e, mod - 1) % (mod - 1), mod) % mod; continue out; } target = target * mul % mod; } throw new AssertionError(); } return ans; } public static long modInv(long a, long mod) { return modPow(a,mod-2,mod); } public static long[] modAdd(long[] a, long[] b, long mod) { if (a.length != b.length) throw new AssertionError(); long[] c = new long[a.length]; for (int i = 0; i < a.length; ++i) { c[i] = a[i] + b[i]; if (c[i] >= mod) c[i] -= mod; } return c; } public static long[] modMul(long[] a, long scalar, long mod) { long[] b = new long[a.length]; for (int i = 0; i < a.length; ++i) { b[i] = a[i] * scalar % mod; } return b; } public static long[] modSub(long[] a, long[] b, long mod) { if (a.length != b.length) throw new AssertionError(); long[] c = new long[a.length]; for (int i = 0; i < a.length; ++i) { c[i] = a[i] - b[i]; if (c[i] < 0) c[i] += mod; } return c; } /** * k = floor(N/i) が等しい区間 1 <= l <= i <= r <= N について組 [l, r, k] を k の昇順(iの降順)に返す。 */ public static ArrayList<long[]> floorRange(long N) { ArrayList<long[]> range=new ArrayList<>(); long quotient=1; while(true) { long upper=N/quotient; long lower=N/(quotient+1)+1; range.add(new long[] {lower, upper, quotient}); if(lower==1)break; quotient=N/(lower-1); } return range; } public static String toFibonacciBaseString(long n) { long[] F=new long[92]; F[0]=F[1]=1; for(int i=2;i<F.length;++i) { F[i]=F[i-1]+F[i-2]; } StringBuilder sb=new StringBuilder(""); for(int i=F.length-1;i>=0;--i) { if(n>=F[i]) { sb.append("1"); n-=F[i]; }else { sb.append("0"); } } return sb.toString(); } /** * a = sum[i] b[i] 10^i となる b を返す * @param a * @return */ int[] digitsArray(long a) { int[] ret=new int[40]; for(int i=0;i<40;++i) { ret[i]=(int)(a%10); a/=10; if(a==0) return Arrays.copyOf(ret, i + 1); } throw new AssertionError(); } static void tr(Object...objects) { System.out.println(Arrays.deepToString(objects)); } } class Main implements Runnable { // Runnableを実装する public static void main(String[] args) { new Thread(null, new Main(), "", 1024 * 1024 * 1024).start(); // 1024MBスタックを確保して実行 } final long mod=998244353; public void run() { FastScanner sc = FastScanner.getInstance(); MyPrintWriter pw = new MyPrintWriter(System.out); String S=sc.next(); char[]xx=S.toCharArray(); int[]n=new int[xx.length]; Arrays.setAll(n, i->(int)(xx[i]-'0')); long[]poly=new long[10]; long[]mahler=new long[10]; Arrays.fill(poly, 1); Arrays.fill(mahler, 1); mahler[8] = 0; long sub=nthMahler(S, 10, new long[] {1}, Polynomial.mul(mahler, poly), mod); sub=(mod-1+sub)%mod; long all=new BigInteger(S).mod(BigInteger.valueOf(mod)).longValue(); System.out.println((all+mod-sub)%mod); pw.close(); } static void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));} /** * [x^n] poly(x)mahler(x)mahler(x^m)mahler(x^{2m})... * @param poly * @param mahler * @return */ long nthMahler(String n, int m, long[] poly, long[] mahler, long mod) { if (mahler[0] != 1) throw new AssertionError(); BigInteger nBigInt=new BigInteger(n); BigInteger mBigInt=BigInteger.valueOf(m); long[] g = Arrays.copyOf(poly, poly.length); while (!nBigInt.equals(BigInteger.ZERO)) { int r = nBigInt.mod(mBigInt).intValue(); long[] f = Polynomial.mul(g, mahler); long[] ng = new long[1 + (f.length - 1 - r) / m]; for (int i = r; i < f.length; i += m) { ng[i / m] = f[i]; } g = ng; nBigInt = nBigInt.divide(mBigInt); } return g[0]; } }