結果
| 問題 |
No.3242 Count 8 Included Numbers (Hard)
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2025-08-23 07:44:13 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 30,578 bytes |
| コンパイル時間 | 4,520 ms |
| コンパイル使用メモリ | 98,304 KB |
| 実行使用メモリ | 44,980 KB |
| 最終ジャッジ日時 | 2025-08-23 07:44:22 |
| 合計ジャッジ時間 | 8,599 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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 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 PolynomialFp {
static long mod = 998244353;
public long[] f;
static long[][] bitreversedRoots = new long[30][];
static long[][] bitreversedInvRoots = new long[30][];
public PolynomialFp(long[] v) {
if (v != null) f = Arrays.copyOf(v, v.length);
}
public static PolynomialFp of(long[] v) {
return new PolynomialFp(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 PolynomialFp mul(long a) {
return new PolynomialFp(mul(f, a));
}
public PolynomialFp mul(PolynomialFp poly) {
return new PolynomialFp(mul(f, poly.f));
}
public PolynomialFp sqrt() {
PolynomialFp poly = new PolynomialFp(null);
poly.f = exp(f);
return poly;
}
public PolynomialFp inv() {
PolynomialFp poly = new PolynomialFp(null);
poly.f = inv(f);
return poly;
}
public PolynomialFp subtract(PolynomialFp p) {
PolynomialFp poly = new PolynomialFp(null);
poly.f = subtract(f, p.f);
return poly;
}
public PolynomialFp add(PolynomialFp p) {
PolynomialFp poly = new PolynomialFp(null);
poly.f = add(f, p.f);
return poly;
}
/**
* f^src/(1-f) を返す
*/
public PolynomialFp geometricSeries(int src) {
return new PolynomialFp(mul(pow(f, src), inv(subtract(new long[] {1}, f))));
}
public PolynomialFp resize(int n) {
return new PolynomialFp(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 PolynomialFp multiplyByX(int repeat) {
PolynomialFp poly = new PolynomialFp(null);
poly.f = multiplyByX(f, repeat);
return poly;
}
public PolynomialFp pow(int n) {
return new PolynomialFp(pow(f, n));
}
public static PolynomialFp motzkin(int n) {
ModInt mi = new ModInt(mod);
PolynomialFp poly = new PolynomialFp(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 PolynomialFp centralTrinomials(int n) {
ModInt mi = new ModInt(mod);
PolynomialFp poly = new PolynomialFp(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 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}, PolynomialFp.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();
if (m == 10) return nthMahlerBase10(n, poly, mahler, mod);
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 = PolynomialFp.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];
}
/**
* [x^n] poly(x)mahler(x)mahler(x^m)mahler(x^{2m})...
* @param poly
* @param mahler
* @return
*/
long nthMahlerBase10(String n, long[] poly, long[] mahler, long mod) {
if (mahler[0] != 1) throw new AssertionError();
int m = 10;
long[] g = Arrays.copyOf(poly, poly.length);
for (int i = 0; i < n.length(); ++i) {
int r = (int) (n.charAt(i) - '0');
long[] f = PolynomialFp.mul(g, mahler);
long[] ng = new long[1 + (f.length - 1 - r) / m];
for (int j = r; j < f.length; j += m) {
ng[j / m] = f[j];
}
g = ng;
}
return g[0];
}
}