시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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로 나눈 값을 출력한다.

예제 입력 1

4
2 222201
1 111001
1 111111
2 222222

예제 출력 1

13
1
1
100
W3sicHJvYmxlbV9pZCI6Ijk1NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWQ1NTkgXHVjMjE5XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWM3N2NcdWM3NzRcdWIyOTQgXHVjNWI0XHViODI0XHVjNmI0IFx1YzIxOFx1ZDU1OSBcdWJiMzhcdWM4MWNcdWI5N2MgXHVjMjE5XHVjODFjXHViODVjIFx1YmMxYlx1YzU1OFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YWUzMFx1ZDU1Y1x1Yzc3NCBcdWM1YmNcdWI5YzggXHViMGE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC4gXHViMGI0XHVjNzdjXHVhZTRjXHVjOWMwIFx1YzIxOVx1YzgxY1x1Yjk3YyBcdWQ1NzRcdWFjYjBcdWQ1NzRcdWM1N2NcdWI5Y2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMTlcdWM4MWNcdWIyOTQgXHViMDk4XHViMjE3XHVjMTQ4IFx1YzVmMFx1YzJiNVx1Yzc3NFx1YjJlNC4gXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yjg1YyBcdWM1YjRcdWI1YTQgTlx1Yzc5MFx1YjlhYyBcdWMyMThcdWI5N2MgXHViMDk4XHViMjA0XHViMjk0IFx1YWNmY1x1YzgxNVx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNzc0XHVkNTc0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJhYTlcdWQ0NWNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIE5cdWM3OTBcdWI5YWMgXHVjMjE4XHViMjk0IFx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IDBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4yXHVjNzkwXHViOWFjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3NFx1YzExYyA2XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWFjZTAgNVx1Yjg1Y1x1YjI5NCBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NCBcdWMyMThcdWIyOTQgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YWMwMD88XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDAgMDYsIDEyLCAxOCwgMjQsIDM2LCA0MiwgNDgsIDU0LCA2NiwgNzIsIDc4LCA4NCwgOTZcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4wXHVjNzQwIFx1YmFhOFx1YjRlMCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjE4XHVjNzg0XHVjNWQwIFx1YzcyMFx1Yzc1OFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1Yzc3Y1x1Yzc3NFx1YjI5NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHViODI0XHVhY2UwIFx1ZDU4OFx1YzljMFx1YjljYywgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWFjMDAgXHViMTA4XHViYjM0IFx1YjljZVx1YzU0NCBcdWIyZTQgXHVhZDZjXHVkNTYwIFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNWVjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjljYyBcdWFkNmNcdWQ1NzRcdWJjZjRcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCAxICZsZTsgVCAmbGU7IDEsMDAwICk8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOCBOXHVhY2ZjIDZcdWFlMDBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWQ1NThcdWIwOThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1Yzc0MCBcdWFkNmNcdWQ1NjAgXHViMmY1XHVjNzc0IE5cdWM3OTBcdWI5YWMgXHVjODE1XHVjMjE4XHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gKCAxICZsZTsgTiAmbGU7IDEwIDxzdXA+MTg8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjQgNlx1Yzc5MFx1YjlhYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgMCwgMSwgMlx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwLCBpXHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YWMwMCAwXHVjNzc0XHViNzdjXHViYTc0IGlcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWM1NDRcdWM1N2MgXHVkNTY4XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgMVx1Yzc3YyBcdWFjYmRcdWM2YjBcdWM1ZDQgaVx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjODM4XHVjNTdjIFx1ZDU2OFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWJhNzAsIDJcdWM3N2MgXHVhY2JkXHVjNmIwXHVjNWQ0IFx1YzBjMVx1YWQwMFx1YzVjNlx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBOXHVjNzkwXHViOWFjIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NTU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWF0aCBIb21ld29yayIsImRlc2NyaXB0aW9uIjoiPHA+WWVzLCB5b3VyIHRlYWNoZXIgZ2F2ZSB5b3UgYW5vdGhlciBoYXJkIG1hdGggaG9tZXdvcmssIGFuZCB5b3UgaGF2ZSB0byBmaW5pc2ggaXQgYmVmb3JlIGl0cyBkZWFkbGluZS48XC9wPlxyXG5cclxuPHA+VGhpcyBob21ld29yayBpcyBhYm91dCB0aGUgZGl2aXNpb24gb3BlcmF0aW9uLCBhbmQgaXQmcnNxdW87cyBhIHByYWN0aWNlIGZvciB0aGUgZGl2aXNpb24gYnkgc21hbGwgbnVtYmVycy4gWW91IGFyZSBhc2tlZCB0byBjb3VudCB0aGUgbm9uLW5lZ2F0aXZlIG51bWJlcnMgd2hpY2ggY29uc2lzdCBvZiBleGFjdGx5IE4gZGlnaXRzIChsZWFkaW5nIHplcm9zIGFyZSBhbGxvd2VkKSwgYW5kIHRoZXkgc2F0aXNmeSBzb21lIGRpdmlzaW9uIHJlcXVpcmVtZW50cywgZm9yIGV4YW1wbGUgbGV0JnJzcXVvO3Mgc2F5IHlvdSB3YW50IHRvIGNvdW50IHRoZSBudW1iZXJzIHdoaWNoIGNvbnNpc3Qgb2YgMiBkaWdpdHMgYW5kIHRoZXkgYXJlIGRpdmlzaWJsZSBieSA2IGFuZCBub3QgZGl2aXNpYmxlIGJ5IDUsIHRoZXNlIGFyZSB0aGUgbnVtYmVycyB3aGljaCBzYXRpc2Z5IHRoZXNlIHJlcXVpcmVtZW50czogMDYsIDEyLCAxOCwgMjQsIDM2LCA0MiwgNDgsIDU0LCA2NiwgNzIsIDc4LCA4NCBhbmQgOTYuPFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCB6ZXJvIGlzIGRpdmlzaWJsZSBieSBhbnkgcG9zaXRpdmUgbnVtYmVyIChjaGVjayB0aGUgdGhpcmQgc2FtcGxlIHRlc3QgY2FzZSkuPFwvcD5cclxuXHJcbjxwPlNvLCB5b3UgZGVjaWRlZCB0byB3cml0ZSBhIHByb2dyYW0gdG8gc29sdmUgdGhpcyBob21ld29yayBmb3IgeW91LCBiZWNhdXNlIE4gY2FuIGJlIHJlYWxseSBsYXJnZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgd2lsbCBiZSBhIHNpbmdsZSBpbnRlZ2VyIFQsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoMSAmbGU7IFQgJmxlOyAxLCAwMDApLiBGb2xsb3dlZCBieSBUIGxpbmVzLCBlYWNoIGxpbmUgcmVwcmVzZW50cyBvbmUgdGVzdCBjYXNlLCBhbmQgY29uc2lzdHMgb2YgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwPHN1cD4xODxcL3N1cD4pIHdoaWNoIGlzIHRoZSBsZW5ndGggb2YgdGhlIG51bWJlcnMgeW91IGFyZSBhc2tlZCB0byBjb3VudCAoYWdhaW4sIGxlYWRpbmcgemVyb3MgYXJlIGFsbG93ZWQpIGZvbGxvd2VkIGJ5IGEgc3BhY2UgdGhlbiBhIHN0cmluZyBvZiA2IGRpZ2l0cyAoZWFjaCBkaWdpdCBpcyAmbHNxdW87MCZyc3F1bzssICZsc3F1bzsxJnJzcXVvOyBvciAmbHNxdW87MiZyc3F1bzspLCB0aGUgaS10aCBkaWdpdCAodGhlIGxlZnQgbW9zdCBkaWdpdCBpcyB0aGUgZGlnaXQgbnVtYmVyIDEpIGlzICZsc3F1bzswJnJzcXVvOyBpZiB0aGUgbnVtYmVycyBzaG91bGRuJnJzcXVvO3QgYmUgZGl2aXNpYmxlIGJ5IGksIGFuZCBpdCZyc3F1bztzICZsc3F1bzsxJnJzcXVvOyBpZiB0aGUgbnVtYmVycyBzaG91bGQgYmUgZGl2aXNpYmxlIGJ5IGksIGFuZCBpdCZyc3F1bztzICZsc3F1bzsyJnJzcXVvOyBpZiB0aGUgbnVtYmVycyBjYW4gYmUgZGl2aXNpYmxlIG9yIG5vdCBkaXZpc2libGUgYnkgaS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IG9uIGEgc2luZ2xlIGxpbmUgb25lIGludGVnZXIsIHRoZSBjb3VudCBvZiB0aGUgbnVtYmVycyB5b3UgYXJlIGFza2VkIHRvIGNvdW50IGFzIGRlc2NyaWJlZCBhYm92ZSwgc2luY2UgdGhlIHJlc3VsdCBtYXkgYmUgdmVyeSBsYXJnZSwgcHJpbnQgaXQgbW9kdWxvIDEsMDAwLDAwMCwwMDcgKCgxMDxzdXA+OTxcL3N1cD4gKyA3KSkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d