짝수로 만들 수 있는 모든 수의 합

문자열 집합의 양의 폐쇄(positive closure)는 그 집합의 원소를 이어 붙여 만들 수 있는, 길이가 유한하고 비어 있지 않은 모든 문자열의 집합이다. 같은 원소를 여러 번 써도 된다. 여기서 원소는 한 자리 숫자이므로 폐쇄의 원소는 모두 수가 된다.

쓸 수 있는 숫자는 짝수 2, 4, 6, 8 네 개뿐이고, 각 숫자를 몇 개까지 쓸 수 있는지 주어진다. 주어진 개수를 넘기지 않으면서 만들 수 있는 수를 모두 만들고, 같은 수는 한 번만 세어 전부 더한다. 합이 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

2를 두 개, 4를 한 개 쓸 수 있다고 하자. 만들 수 있는 서로 다른 수는 2, 4, 22, 24, 42, 224, 242, 422 여덟 개이고, 그 합은 982다. 2가 두 개 있어도 수 2는 한 번만 센다.

쓸 수 있는 짝수가 하나도 없으면 만들 수 있는 수가 없으므로 합은 0이다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 500$)가 주어진다.

다음 $T$개의 줄에는 각각 아홉 개의 정수 $P_1, P_2, \dots, P_9$ ($0 \le P_i \le 9$)가 주어진다. $P_i$는 숫자 $i$를 쓸 수 있는 개수다. 홀수에 해당하는 $P_1, P_3, P_5, P_7, P_9$도 입력에 들어오지만, 수에는 짝수만 넣을 수 있으므로 쓰이지 않는다.

각 테스트 케이스마다 Case #x: M 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $M$은 만들 수 있는 모든 수의 합을 1,000,000,007로 나눈 나머지다.