수학 숙제

동일이는 어려운 수학 숙제를 받았다. 기한이 내일까지라 시간이 얼마 없다.

숙제는 나눗셈 연습이다. 작은 수로 $N$자리 수를 나누는 과정을 익히는 것이 목표다. 여기서 $N$자리 수는 0으로 시작해도 된다. 앞에 0이 몇 개 붙어 있어도 $N$자리 수로 센다.

숙제의 물음은 모두 다음 형태다.

2자리 정수 중에서 6으로 나누어떨어지고 5로는 나누어떨어지지 않는 수는 몇 개인가?

이 물음의 답은 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84, 96이므로 13개다.

0은 모든 양의 정수로 나누어떨어진다는 점에 유의한다.

조건을 만족하는 수가 너무 많아 하나씩 적기는 어렵다고 본 동일이는 개수만 구하기로 했다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1000$)

이어지는 $T$개의 줄에 각각 정수 $N$과 길이 6인 문자열이 공백으로 구분되어 주어진다.

$N$은 세려는 수가 $N$자리임을 뜻한다. ($1 \le N \le 10^{18}$)

문자열은 0, 1, 2로만 이루어져 있다. $i$번째 글자가 0이면 그 수는 $i$로 나누어떨어지지 않아야 하고, 1이면 $i$로 나누어떨어져야 하며, 2이면 $i$로 나누어떨어지는지는 상관없다. ($1 \le i \le 6$)

각 테스트 케이스마다 조건을 만족하는 $N$자리 수의 개수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.