29705번 - 문자열 만들기

문제

알파벳 대문자 ‘A-Z’, 알파벳 소문자 ‘a-z’, 숫자 ‘0-9’를 원소로 가지는 집합 $C$의 부분 집합 $P$를 정의역으로 하는 함수 $f(c)$가 있다. $f(c)$의 값은 1ドル$ 이상 9ドル$ 이하의 자연수이다.

1ドル$ 이상 9ドル$ 이하인 자연수 $i$에 대해 집합 $S_i$를 다음과 같이 정의하자. 즉, $S_i$는 집합 $P$의 원소 중, 함수 $f$에 대한 함숫값이 $i$가 되는 문자들의 집합이다.

$$S_i=\{c \in P | f(c)=i\}$$

$S_i$에 속하는 문자가 각각 주어질 때, 다음 함수 $g(x)$의 값이 $a$ 이상 $b$ 이하가 되도록 하는 서로 다른 $x$의 개수를 구하여 보자.

$$g(x)=\sum_{i=1}^{\lvert x \rvert}{f(x_i)}$$

단, $x$는 $P$에 속한 문자들을 이어 붙여 만든 길이가 1ドル$ 이상인 문자열이고, $x_i$는 $x$의 $i$번째 문자이다. 또, $\lvert x \rvert$는 문자열 $x$의 길이를 의미한다.

입력

첫째 줄에 정수 $a$와 $b$가 공백을 기준으로 주어진다. $(1 \leq a \leq b ≤ 10^{18};$ $b - a \lt 5,000円,000円)$

둘째 줄부터 열 번째 줄까지 $S_i$의 모든 문자가 $(i + 1)$번째 줄에 공백 없이 주어진다.

집합 $S_i$의 원소의 개수는 1ドル$ 이상 50ドル$ 이하이다.

주어지는 모든 문자는 알파벳 대소문자, 숫자로 구성되어 있고 각 문자는 최대 한 번씩만 등장한다.

출력

서로 다른 $x$의 개수를 1ドル,000円,000円,007円(=10^9 + 7)$로 나눈 나머지를 출력한다. 이 수는 소수이다.

제한

힌트