Informatica Online Judge

  고딩(K-div Number) [0225 / 00E1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 62   Total Tried : 73


The Champion of this Problem (C++) : justinwk - 2ms / 488byte
My Best Submission (C++) : N/A

[]

Background

어떤 숫자가 K로 나누어 떨어지면 그 수를 "K-Div Number"이라고 한다. 20은 4-Div Number이지만 14는 그렇지 않다.

184는 4-Div Number이고 121은 그렇지 않다. 다만 0은 모든 K에 대해 K-Div Number라고 부른다. 물른 이는 음수에 대해서도 성립한다. -20과 -184는 4-Div Number라고 할 수 있다.

당신은 모처럼 한가한 시간을 보내고 있었다. 그러던 중 "123445"이 쓰여진 종이를 발견하고, 이 숫자들 사이에 +나 -부호를 넣어서 얼마나 많은 7-Div Number가 나오는지 궁금했다.(K를 7로 정한 이유는 이 숫자를 가장 좋아하기 때문이다.)

예를 들어 1+2+3+4+5+6=21이 되어 이 수는 7-Div Number이다. 하지만 123+4-56=71과 같이 수정하면 7-Div Number가 아니다.

얼마나 다양한 경우가 나오는지 계산해 보았다. 이 경우 각 숫자들 사이에 +,-를 넣거나, 아무것도 넣지 않는 경우가 있으므로 D자리의 숫자가 있으면 3^(D-1)가지의 경우가 생긴다. 이 숫자는 앞에 나오는 0을 무시하지 않는다.

즉 "01023"이 입력으로 들어오면 "01023", "0+1-02+3", "01-023" 등도 모두 올바른 수식이다.

당신이 해야할 일은 간단하다. D자리의 숫자와 자연수 K가 주어질 때. 3^(D-1)가지의 경우 중에서 K-Div Number가 나오는 경우가 얼마나 되는지 구하여라.

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1<=T<=30)
두 번째 줄 부터 T+1번째 줄까지는 자연수 K와 숫자열 S가 주어진다.(1<=K<=100, S는 100자리 이하의 수)

Output

각각의 테스트 케이스에 대해 조건을 만족하는 경우와 개수를 1,000,000,007로 나눈 나머지를 출력한다.

IO Example

입력
2
7 1234
9 123456

출력
4
38

출제 : 윤형석(IOI-09 금메달리스트)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]