Dongmin Sequence

Time limit2sMemory limit128 MB

Summary

Count sequences of lucky numbers (digits 4/7 only) chosen from a given list of length L, where consecutive elements share first/last digit, modulo 1,234,567,891.

Level: Medium6 of 10
Topics: Matrix, Dynamic programming, Math, Graph
Solved: No attempts yet

Problem

Eunmin likes only the digits 4 and 7. In this problem, a positive decimal integer whose every digit is either 4 or 7 is called a lucky number.

A Dongmin sequence is a sequence A[0], A[1], ..., A[L-1] of length L. It must satisfy all of the following conditions.

Each A[i] is a lucky number.
Each A[i] appears at least once in the given Numbers array.
For every 0 ≤ i < L-1, the last digit of A[i] is equal to the first digit of A[i+1].

If the same value appears multiple times in Numbers, choosing that value still counts as the same sequence element. Given Numbers and L, compute the number of distinct Dongmin sequences modulo 1,234,567,891.

Input

The first line contains the size N of the Numbers array and the sequence length L. N is a positive integer no greater than 50, and L is a positive integer no greater than 1,000,000,000.

The second line contains the N elements of Numbers. Each element is a positive integer no greater than 1,000,000,000.

Output

Print the number of distinct Dongmin sequences modulo 1,234,567,891.

Examples4

Example 1
Input
```
5 47
100 4774 200 747 300
```
Expected output
```
2
```
Example 2
Input
```
10 1
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
2
```
Example 3
Input
```
3 3
47 74 47
```
Expected output
```
2
```
Example 4
Input
```
4 2
44 47 74 77
```
Expected output
```
8
```