9606: ABC246 —— F - typewriter
[Creator : ]
Description
We have a typewriter with $N$ rows. The keys in the $i$\-th row from the top can type the characters in a string $S_i$.
Let us use this keyboard to enter a string, as follows.
- First, choose an integer $1 \le k \le N$.
- Then, start with an empty string and only use the keys in the $k$\-th row from the top to enter a string of length exactly $L$.
How many strings of length $L$ can be entered in this way? Since the answer can be enormous, print it modulo $998244353$.
Let us use this keyboard to enter a string, as follows.
- First, choose an integer $1 \le k \le N$.
- Then, start with an empty string and only use the keys in the $k$\-th row from the top to enter a string of length exactly $L$.
How many strings of length $L$ can be entered in this way? Since the answer can be enormous, print it modulo $998244353$.
Input
Input is given from Standard Input in the following format:
```
$N$ $L$
$S_1$
$S_2$
$\dots$
$S_N$
```
```
$N$ $L$
$S_1$
$S_2$
$\dots$
$S_N$
```
Output
Print the answer.
Constraints
- $N$ and $L$ are integers.
- $1 \le N \le 18$
- $1 \le L \le 10^9$
- $S_i$ is a (not necessarily contiguous) non-empty subsequence of `abcdefghijklmnopqrstuvwxyz`.
- $1 \le N \le 18$
- $1 \le L \le 10^9$
- $S_i$ is a (not necessarily contiguous) non-empty subsequence of `abcdefghijklmnopqrstuvwxyz`.
Sample 1 Input
2 2
ab
ac
Sample 1 Output
7
We can enter seven strings: aa, ab, ac, ba, bb, ca, cc.
Sample 2 Input
4 3
abcdefg
hijklmnop
qrstuv
wxyz
Sample 2 Output
1352
Sample 3 Input
5 1000000000
abc
acde
cefg
abcfh
dghi
Sample 3 Output
346462871