1529번 - 동민 수열

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

동민 수열은 길이가 L이고, A[0], A[1], ..., A[L-1]와 같이 생긴 수열이다. 또, 다음과 같은 성질을 가진다.

1. A[i]는 금민수이다. (0 ≤ i < L)
2. 모든 i에 대해서 A[i] = Numbers[j]인 j가 적어도 하나 존재한다. (0 ≤ i < L)
3. 모든 i에 대해서 A[i]의 마지막 자리는 A[i+1]의 첫 번째 자리와 같다. (0 ≤ i < L-1)

Numbers배열과 L이 주어졌을 때, 서로 다른 동민 수열의 개수를 1,234,567,891로 나눈 나머지를 출력하는 프로그램을 작성하시오.

첫째 줄에 Numbers 배열의 크기 N과 L이 주어진다. N은 50보다 작거나 같은 자연수이고, L은 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄에 Numbers배열에 들어있는 수가 주어진다. 각각의 수는 1,000,000,000보다 작거나 같은 자연수이다.

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