시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB125342836.364%

문제

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

숙제는 나눗셈 연습이다. 작은 수로 어떤 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로 나눈 값을 출력한다.

예제 입력 1

4
2 222201
1 111001
1 111111
2 222222

예제 출력 1

13
1
1
100
W3sicHJvYmxlbV9pZCI6Ijk1NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWQ1NTkgXHVjMjE5XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWM3N2NcdWM3NzRcdWIyOTQgXHVjNWI0XHViODI0XHVjNmI0IFx1YzIxOFx1ZDU1OSBcdWJiMzhcdWM4MWNcdWI5N2MgXHVjMjE5XHVjODFjXHViODVjIFx1YmMxYlx1YzU1OFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YWUzMFx1ZDU1Y1x1Yzc3NCBcdWM1YmNcdWI5YzggXHViMGE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC4gXHViMGI0XHVjNzdjXHVhZTRjXHVjOWMwIFx1YzIxOVx1YzgxY1x1Yjk3YyBcdWQ1NzRcdWFjYjBcdWQ1NzRcdWM1N2NcdWI5Y2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMTlcdWM4MWNcdWIyOTQgXHViMDk4XHViMjE3XHVjMTQ4IFx1YzVmMFx1YzJiNVx1Yzc3NFx1YjJlNC4gXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yjg1YyBcdWM1YjRcdWI1YTQgTlx1Yzc5MFx1YjlhYyBcdWMyMThcdWI5N2MgXHViMDk4XHViMjA0XHViMjk0IFx1YWNmY1x1YzgxNVx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNzc0XHVkNTc0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJhYTlcdWQ0NWNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgTlx1Yzc5MFx1YjlhYyBcdWMyMThcdWIyOTQgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggMFx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjJcdWM3OTBcdWI5YWMgXHVjODE1XHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjIDZcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YWNlMCA1XHViODVjXHViMjk0IFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzIxOFx1YjI5NCBcdWJhODcgXHVhYzFjXHVjNzc4XHVhYzAwPzxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1Yzc0MCAwNiwgMTIsIDE4LCAyNCwgMzYsIDQyLCA0OCwgNTQsIDY2LCA3MiwgNzgsIDg0LCA5Nlx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjBcdWM3NDAgXHViYWE4XHViNGUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWM3ODRcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVjNzdjXHVjNzc0XHViMjk0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWI4MjRcdWFjZTAgXHVkNTg4XHVjOWMwXHViOWNjLCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNTQ0IFx1YjJlNCBcdWFkNmNcdWQ1NjAgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWM1ZWMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOWNjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1YjgyNCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoIDEgJmxlOyBUICZsZTsgMSwwMDAgKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4IE5cdWFjZmMgNlx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVjNzQwIFx1YWQ2Y1x1ZDU2MCBcdWIyZjVcdWM3NzQgTlx1Yzc5MFx1YjlhYyBcdWM4MTVcdWMyMThcdWM3ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiAoIDEgJmxlOyBOICZsZTsgMTAgPHN1cD4xODxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNCA2XHVjNzkwXHViOWFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAwLCAxLCAyXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWIzNzAsIGlcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVhYzAwIDBcdWM3NzRcdWI3N2NcdWJhNzQgaVx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NjhcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCAxXHVjNzdjIFx1YWNiZFx1YzZiMFx1YzVkNCBpXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM4MzhcdWM1N2MgXHVkNTY4XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgMlx1Yzc3YyBcdWFjYmRcdWM2YjBcdWM1ZDQgXHVjMGMxXHVhZDAwXHVjNWM2XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IE5cdWM3OTBcdWI5YWMgXHVjODE1XHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijk1NTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYXRoIEhvbWV3b3JrIiwiZGVzY3JpcHRpb24iOiI8cD5ZZXMsIHlvdXIgdGVhY2hlciBnYXZlIHlvdSBhbm90aGVyIGhhcmQgbWF0aCBob21ld29yaywgYW5kIHlvdSBoYXZlIHRvIGZpbmlzaCBpdCBiZWZvcmUgaXRzIGRlYWRsaW5lLjxcL3A+XHJcblxyXG48cD5UaGlzIGhvbWV3b3JrIGlzIGFib3V0IHRoZSBkaXZpc2lvbiBvcGVyYXRpb24sIGFuZCBpdCZyc3F1bztzIGEgcHJhY3RpY2UgZm9yIHRoZSBkaXZpc2lvbiBieSBzbWFsbCBudW1iZXJzLiBZb3UgYXJlIGFza2VkIHRvIGNvdW50IHRoZSBub24tbmVnYXRpdmUgbnVtYmVycyB3aGljaCBjb25zaXN0IG9mIGV4YWN0bHkgTiBkaWdpdHMgKGxlYWRpbmcgemVyb3MgYXJlIGFsbG93ZWQpLCBhbmQgdGhleSBzYXRpc2Z5IHNvbWUgZGl2aXNpb24gcmVxdWlyZW1lbnRzLCBmb3IgZXhhbXBsZSBsZXQmcnNxdW87cyBzYXkgeW91IHdhbnQgdG8gY291bnQgdGhlIG51bWJlcnMgd2hpY2ggY29uc2lzdCBvZiAyIGRpZ2l0cyBhbmQgdGhleSBhcmUgZGl2aXNpYmxlIGJ5IDYgYW5kIG5vdCBkaXZpc2libGUgYnkgNSwgdGhlc2UgYXJlIHRoZSBudW1iZXJzIHdoaWNoIHNhdGlzZnkgdGhlc2UgcmVxdWlyZW1lbnRzOiAwNiwgMTIsIDE4LCAyNCwgMzYsIDQyLCA0OCwgNTQsIDY2LCA3MiwgNzgsIDg0IGFuZCA5Ni48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHplcm8gaXMgZGl2aXNpYmxlIGJ5IGFueSBwb3NpdGl2ZSBudW1iZXIgKGNoZWNrIHRoZSB0aGlyZCBzYW1wbGUgdGVzdCBjYXNlKS48XC9wPlxyXG5cclxuPHA+U28sIHlvdSBkZWNpZGVkIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBzb2x2ZSB0aGlzIGhvbWV3b3JrIGZvciB5b3UsIGJlY2F1c2UgTiBjYW4gYmUgcmVhbGx5IGxhcmdlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCB3aWxsIGJlIGEgc2luZ2xlIGludGVnZXIgVCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICgxICZsZTsgVCAmbGU7IDEsIDAwMCkuIEZvbGxvd2VkIGJ5IFQgbGluZXMsIGVhY2ggbGluZSByZXByZXNlbnRzIG9uZSB0ZXN0IGNhc2UsIGFuZCBjb25zaXN0cyBvZiBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTA8c3VwPjE4PFwvc3VwPikgd2hpY2ggaXMgdGhlIGxlbmd0aCBvZiB0aGUgbnVtYmVycyB5b3UgYXJlIGFza2VkIHRvIGNvdW50IChhZ2FpbiwgbGVhZGluZyB6ZXJvcyBhcmUgYWxsb3dlZCkgZm9sbG93ZWQgYnkgYSBzcGFjZSB0aGVuIGEgc3RyaW5nIG9mIDYgZGlnaXRzIChlYWNoIGRpZ2l0IGlzICZsc3F1bzswJnJzcXVvOywgJmxzcXVvOzEmcnNxdW87IG9yICZsc3F1bzsyJnJzcXVvOyksIHRoZSBpLXRoIGRpZ2l0ICh0aGUgbGVmdCBtb3N0IGRpZ2l0IGlzIHRoZSBkaWdpdCBudW1iZXIgMSkgaXMgJmxzcXVvOzAmcnNxdW87IGlmIHRoZSBudW1iZXJzIHNob3VsZG4mcnNxdW87dCBiZSBkaXZpc2libGUgYnkgaSwgYW5kIGl0JnJzcXVvO3MgJmxzcXVvOzEmcnNxdW87IGlmIHRoZSBudW1iZXJzIHNob3VsZCBiZSBkaXZpc2libGUgYnkgaSwgYW5kIGl0JnJzcXVvO3MgJmxzcXVvOzImcnNxdW87IGlmIHRoZSBudW1iZXJzIGNhbiBiZSBkaXZpc2libGUgb3Igbm90IGRpdmlzaWJsZSBieSBpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb24gYSBzaW5nbGUgbGluZSBvbmUgaW50ZWdlciwgdGhlIGNvdW50IG9mIHRoZSBudW1iZXJzIHlvdSBhcmUgYXNrZWQgdG8gY291bnQgYXMgZGVzY3JpYmVkIGFib3ZlLCBzaW5jZSB0aGUgcmVzdWx0IG1heSBiZSB2ZXJ5IGxhcmdlLCBwcmludCBpdCBtb2R1bG8gMSwwMDAsMDAwLDAwNyAoKDEwPHN1cD45PFwvc3VwPiArIDcpKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d