Dongmin Sequence

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.

1. Each A[i] is a lucky number.
2. Each A[i] appears at least once in the given Numbers array.
3. 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.

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.

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