B. Firefly's Favourite Problem
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$N$$$ and a digit $$$x$$$ ($$$1 \le x \le 9$$$). Let $$$n$$$ be the number of digits of the decimal representation of $$$N$$$. For example, if $$$N=10000$$$, then $$$n=5$$$; if $$$N=114514$$$, then $$$n=6$$$.

Define $$$g(M)$$$ to be the number of occurrences of the digit $$$x$$$ in the decimal representation of $$$M$$$. For example, if $$$x=6$$$, then $$$g(1)=0$$$, $$$g(666)=3$$$, and $$$g(16161)=2$$$.

For each integer $$$k$$$ with $$$0 \le k \le n$$$, let $$$f(k)$$$ be the number of positive integers $$$M \le N$$$ for which $$$g(M)=k$$$.

Your task is to compute $$$f(k) \bmod {998244353}$$$ for every $$$0 \le k \le n$$$.

Input

The first line of each test contains the integer $$$N$$$ ($$$1 \le N \le 10^{200000}$$$).

The second line contains the digit $$$x$$$ ($$$1 \le x \le 9$$$).

Output

Output $$$n+1$$$ integers, the $$$i$$$-th one being $$$f(i-1) \bmod {998244353}$$$.

Examples
Input
114514
1
Output
59048 39366 12726 2912 428 33 1
Input
1919810
9
Output
1062881 662661 169786 22744 1673 64 1 0
Input
1
2
Output
1 0