문제
진욱이는 4와 7이란 숫자를 좋아한다. 그래서 4와 7로만 이루어진 수를 행운의 수라고 부른다.
길이가 L인 행운의 수열 : A[0], A[1], ... , A[L-1]은 아래와 같은 조건을 만족한다.
전체조건 : 임의의 배열 numbers가 존재하며, 수열 A의 모든 숫자는 행운의 수여야 한다.
조건1 : 0 <= i < L를 만족하는 모든 i에 대해서 A[i]가 numbers[j]와 같은 j가 하나 이상 존재한다.
조건2 : 0 <= i < L-1를 만족하는 모든 i에 대해서 A[i]의 끝자리는 A[i+1]의 첫 자리와 같다.(끝말잇기)
임의의 정수 배열 numbers와 L가 주어졌을 때 서로 다른 행운의 수열의 경우의 수를 1234567891로 나눈 나머지를 구하시오.
입력
입력은 한 줄로 이뤄지는데, 첫 번째는 numbers의 배열의 원소의 개수 N(1 <= N <=50)이 입력되며,
N개의 numbers 배열의 숫자들이 1 이상 1,000,000,000 이하의 범위로 입력되다.
그 다음에는 행운의 수열을 위한 1 이상 1,000,000,000 이하의 정수 L이 입력된다.
출력
입력에 대해 문제의 조건을 만족시키는 서로 다른 행운의 수열의 경우의 수를 1234567891로 나눈 나머지를 출력한다.
예제
3 47 74 47 3
2
로그인해야 코드를 작성할 수 있어요.