동민 수열

은민이는 숫자 4와 7만 좋아한다. 이 문제에서는 십진수의 모든 자릿수가 4 또는 7인 양의 정수를 행운수라고 한다.

동민 수열은 길이가 L인 수열 A[0], A[1], ..., A[L-1]이다. 이 수열은 다음 조건을 모두 만족해야 한다.

1. 각 A[i]는 행운수이다.
2. 각 A[i]는 주어진 Numbers 배열에 적어도 한 번 등장하는 값이다.
3. 모든 0 ≤ i < L-1에 대해 A[i]의 마지막 자릿수는 A[i+1]의 첫 번째 자릿수와 같다.

Numbers 배열에 같은 값이 여러 번 들어 있어도, 수열의 원소 값이 같으면 같은 선택으로 본다. Numbers 배열과 L이 주어질 때 만들 수 있는 서로 다른 동민 수열의 개수를 1,234,567,891로 나눈 나머지를 구하라.

첫째 줄에 Numbers 배열의 크기 N과 수열의 길이 L이 주어진다. N은 50 이하의 자연수이고, L은 1,000,000,000 이하의 자연수이다.

둘째 줄에는 Numbers 배열의 원소 N개가 주어진다. 각 원소는 1,000,000,000 이하의 자연수이다.

서로 다른 동민 수열의 개수를 1,234,567,891로 나눈 나머지를 출력한다.