문제
1부터 9까지 숫자에 대해 각 숫자마다 총 몇개의 숫자를 최대로 사용할 수 있는지가 주어졌을 때,
만들 수 있는 숫자의 전체 합을 구하는 프로그램을 작성하라. 단 모든 숫자를 사용할 필요는 없다.
예를 들어 다음과 같이 사용할 수 있는 각 숫자의 개수가 주어져 있다고 하자.
위의 표는 2는 최대 2개를 쓸 수 있고, 4와 6은 최대 한개를 사용할 수 있다는 것을 의미한다. 위의 표에 사용 가능한 자릿수를 맞춰서 생성할 수 있는 숫자는 32개이며 다음과 같다.
2, 4, 6, 22, 24, 26, 42, 46, 62, 64, 224, 226, 242, 246, 262, 264, 422, 426, 462,
622, 624, 642, 2246, 2264, 2426, 2462, 2624, 2642, 4226, 4262, 4622, 6224, 6242, 6422.
그리고 이들의 합은 51622이다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 입력된다( T<=50 ). 각 테스트 케이스는 한 줄로 이뤄지며 총 9개의 9이하의 정수가 들어온다. 각 숫자는 앞에부터 사용할 수 있는 1의 개수, 2의 개수, ..., 9의 개수를 의미한다.
출력
테스트 케이스에 대해 만들 수 있는 숫자들의 총 합을 1,000,000,007로 나눈 나머지를 출력한다.
예제
3
0 0 1 0 1 0 0 0 0
0 2 0 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1
96
51622
454976431
출처
acm-icpc jakarta 2010
로그인해야 코드를 작성할 수 있어요.