문제 1037 덧셈뺄셈(2)
[만든사람 : ]
문제 설명
초등학교를 졸업한 세종이는 중학교에 입학했다.
수학을 좋아하는 세종이는 숫자들이 나열된 수열 중간중간에 기호를 삽입해서 어떤 값을 만드는 것을 좋아한다. 이 때 사용하는 기호는 '+', '-', '결합'이다.
하지만, 기호들을 통해 만들어지는 중간중간의 결과가 음수이거나 700보다 큰 경우에는 계산이 너무 어려워서 어떤 값을 만들어낼 수가 없다.
만약 1 과 2가 주어진다면, 각 연산의 결과는 다음과 같다.
1부터 9로 구성된 n개의 숫자가 주어질 때, 이 숫자들 사이에 '+', '-', '결합'을 사용하여 어떤 값 k를 만들 수 있는 경우의 수를 구해보자.
수학을 좋아하는 세종이는 숫자들이 나열된 수열 중간중간에 기호를 삽입해서 어떤 값을 만드는 것을 좋아한다. 이 때 사용하는 기호는 '+', '-', '결합'이다.
하지만, 기호들을 통해 만들어지는 중간중간의 결과가 음수이거나 700보다 큰 경우에는 계산이 너무 어려워서 어떤 값을 만들어낼 수가 없다.
만약 1 과 2가 주어진다면, 각 연산의 결과는 다음과 같다.
- 1 + 2 ('+'를 사용하여 3)
- 1 - 2 ('-'를 사용하여 -1, 이 경우는 음수가 되기 때문에 사용할 수가 없다)
- 12 ('결합'을 사용하여 12)
1부터 9로 구성된 n개의 숫자가 주어질 때, 이 숫자들 사이에 '+', '-', '결합'을 사용하여 어떤 값 k를 만들 수 있는 경우의 수를 구해보자.
입력 설명
첫 번째 줄에 수열의 길이 n이 주어진다.
두 번째 줄에 원하는 수 k가 주어진다.
세 번째 줄에는 1~9까지의 숫자 n개가 공백으로 구분되어 주어진다.
(1 <= n <= 100)
(1 <= k <= 800)
두 번째 줄에 원하는 수 k가 주어진다.
세 번째 줄에는 1~9까지의 숫자 n개가 공백으로 구분되어 주어진다.
(1 <= n <= 100)
(1 <= k <= 800)
출력 설명
가능한 경우의 수를 출력한다. 단, 수가 너무 커질 수 있으므로 결과를 10억 7로 나눈 나머지를 출력한다.
입력 예시 복사
3
9
1 2 3
출력 예시 복사
1
출처/분류