Given $m$ template strings. For a given string, we can partition it into several segments; if after partitioning, $t$ segments are each equal to one of the template strings, the value of this partition is $t$. The value of a string is defined as the maximum value among all possible partitions.

Banban wants to know how many numeric strings of length $2n$ exist such that the first $n$ digits are equal to the last $n$ digits, and the value of the string does not exceed $k$.

Input

The first line contains three integers $n$, $m$, and $k$.

The next $m$ lines each contain a numeric string, representing each template string.

Output

Output the number of strings satisfying the condition, modulo $1,000,000,007$.

Examples

Input 1

2 2 0
23
41

Output 1

96

Note 1

The 4 invalid strings are 23|23, 3|23|2, 41|41, and 1|41|4. The vertical bars in each number represent a partition scheme with a value exceeding $0$.

Input 2

5 2 3
23
41

Output 2

99880

Subtasks

Subtask 1 (6 points): $n\le 5, m\le 10$.

Subtask 2 (9 points): Each template string has a length of $1$.

Subtask 3 (18 points): $n\le 20, m\le 50$.

Subtask 4 (15 points): $k = 0$.

Subtask 5 (13 points): $k = 1$.

Subtask 6 (19 points): $k = 2$.

Subtask 7 (20 points): No special restrictions.

For all data, $n\le 100$, $m\le 200$, $k\le 3$, and the length of each template string does not exceed $5$.

After submitting your code, the pretest data will be evaluated and the results will be returned. This problem's pretest data contains 7 test cases, each with data scale limits corresponding to the numbered subtasks.

Note: The evaluation results of the pretest data have no relation to the final evaluation results.