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=0;
		for(int i=0;i<n.length;++i) {
			all*=10;
			all+=n[i];
			all%=mod;
		}
		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];
	}
}