1부터 9까지의 한자리 수를 여러 개 줄게. 숫자를 하나 이상 사용해서 만들 수 있는 모든 수를 더해 봐.

예를 들어 위처럼 2가 2개, 4가 1개, 6이 1개 있다면, 우리가 만들 수 있는 수는 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로 총 32개고, 얘네들의 합은 51622야.

뭐해. 빨리 더해.

입력 형식

첫째 줄에 테스트 케이스의 수 T (T ≤ 500) 이 주어진다.

각 테스트 케이스는 9개의 정수 P_i (0 ≤ P_i ≤ 9) 로 이루어져 있으며, 각 정수는 i=1~9에 대해 숫자 i의 개수를 의미한다.

출력 형식

각 테스트 케이스마다, 문제의 답을 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