{"problem":{"name":"typewriter","description":{"content":"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 in","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc246_f"},"statements":[{"statement_type":"Markdown","content":"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$.\nLet us use this keyboard to enter a string, as follows.\n\n*   First, choose an integer $1 \\le k \\le N$.\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$.\n\nHow many strings of length $L$ can be entered in this way? Since the answer can be enormous, print it modulo $998244353$.\n\n## Constraints\n\n*   $N$ and $L$ are integers.\n*   $1 \\le N \\le 18$\n*   $1 \\le L \\le 10^9$\n*   $S_i$ is a (not necessarily contiguous) non-empty subsequence of `abcdefghijklmnopqrstuvwxyz`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $L$\n$S_1$\n$S_2$\n$\\dots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc246_f","tags":[],"sample_group":[["2 2\nab\nac","7\n\nWe can enter seven strings: `aa`, `ab`, `ac`, `ba`, `bb`, `ca`, `cc`."],["4 3\nabcdefg\nhijklmnop\nqrstuv\nwxyz","1352"],["5 1000000000\nabc\nacde\ncefg\nabcfh\ndghi","346462871\n\nBe sure to print the answer modulo $998244353$."]],"created_at":"2026-03-03 11:01:13"}}