Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

data structures

dp

matrices

string suffix structures

strings

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Chainword

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA chainword is a special type of crossword. As most of the crosswords do, it has cells that you put the letters in and some sort of hints to what these letters should be.

The letter cells in a chainword are put in a single row. We will consider chainwords of length $$$m$$$ in this task.

A hint to a chainword is a sequence of segments such that the segments don't intersect with each other and cover all $$$m$$$ letter cells. Each segment contains a description of the word in the corresponding cells.

The twist is that there are actually two hints: one sequence is the row above the letter cells and the other sequence is the row below the letter cells. When the sequences are different, they provide a way to resolve the ambiguity in the answers.

You are provided with a dictionary of $$$n$$$ words, each word consists of lowercase Latin letters. All words are pairwise distinct.

An instance of a chainword is the following triple:

- a string of $$$m$$$ lowercase Latin letters;
- the first hint: a sequence of segments such that the letters that correspond to each segment spell a word from the dictionary;
- the second hint: another sequence of segments such that the letters that correspond to each segment spell a word from the dictionary.

Note that the sequences of segments don't necessarily have to be distinct.

Two instances of chainwords are considered different if they have different strings, different first hints or different second hints.

Count the number of different instances of chainwords. Since the number might be pretty large, output it modulo $$$998\,244\,353$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 8$$$, $$$1 \le m \le 10^9$$$) — the number of words in the dictionary and the number of letter cells.

Each of the next $$$n$$$ lines contains a word — a non-empty string of no more than $$$5$$$ lowercase Latin letters. All words are pairwise distinct.

Output

Print a single integer — the number of different instances of chainwords of length $$$m$$$ for the given dictionary modulo $$$998\,244\,353$$$.

Examples

Input

3 5 ababa ab a

Output

11

Input

2 4 ab cd

Output

4

Input

5 100 a aa aaa aaaa aaaaa

Output

142528942

Note

Here are all the instances of the valid chainwords for the first example:

The red lines above the letters denote the segments of the first hint, the blue lines below the letters denote the segments of the second hint.

In the second example the possible strings are: "abab", "abcd", "cdab" and "cdcd". All the hints are segments that cover the first two letters and the last two letters.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/29/2024 08:18:21 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|