시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 5 4 28.571%

문제

동일이는 어려운 수학 문제를 숙제로 받았다. 이제 기한이 얼마 남지 않았다. 내일까지 숙제를 해결해야만 한다.

숙제는 나눗셈 연습이다. 작은 수로 어떤 N자리 수를 나누는 과정에 대해 이해하는 것이 목표이다. 이 때, N자리 수는 한 개 이상의 0으로 시작할 수도 있다.

문제는 아래와 같은 형식으로 이루어져 있다.

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

이에 대한 답은 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84, 96이 된다.

0은 모든 양의 정수로 나누어 떨어지는 수임에 유의해야 한다.

동일이는 문제를 풀려고 했지만, 조건을 만족하는 수가 너무 많아 다 구할 수가 없다고 생각하여 조건을 만족하는 수의 개수만 구해보려 한다.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 1,000 )

각 테스트 케이스는 하나의 정수 N과 6글자로 이루어진 문자열 하나로 이루어져 있다.

N은 구할 답이 N자리 정수임을 의미한다. ( 1 ≤ N ≤ 10 18)

이어 6자리 문자열은 0, 1, 2로 구성되어 있는데, i번째 글자가 0이라면 i로 나누어 떨어지지 않아야 함을 의미하며, 1일 경우엔 i로 나누어 떨어져야 함을 의미하며, 2일 경우엔 상관없음을 의미한다.

출력

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

예제 입력

4
2 222201
1 111001
1 111111
2 222222

예제 출력

13
1
1
100

힌트