시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 5 5 35.714%

문제

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

Digit 1 2 3 4 5 6 7 8 9
Frequency 0 2 0 1 0 1 0 0 0

예를 들어 위처럼 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개의 정수 Pi (0 ≤ Pi ≤ 9) 로 이루어져 있으며, 각 정수는 i=1~9에 대해 숫자 i의 개수를 의미한다.

출력

각 테스트 케이스마다, 문제의 답을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

96
51622
454976431

힌트

W3sicHJvYmxlbV9pZCI6Ijc4MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzNTRcdWQ1NzQiLCJkZXNjcmlwdGlvbiI6IjxwPjFcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWQ1NWNcdWM3OTBcdWI5YWMgXHVjMjE4XHViOTdjIFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjOTA0XHVhYzhjLiBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMSBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxOFx1Yjk3YyBcdWIzNTRcdWQ1NzQgXHViZDEwLjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NDAlXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+RGlnaXQ8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjY8XC90ZD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjg8XC90ZD5cclxuXHRcdFx0PHRkPjk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+RnJlcXVlbmN5PFwvdGg+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzcwNFx1Y2M5OFx1YjdmYyAyXHVhYzAwIDJcdWFjMWMsIDRcdWFjMDAgMVx1YWMxYywgNlx1Yzc3NCAxXHVhYzFjIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjNmIwXHViOWFjXHVhYzAwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCAyLCA0LCA2LCAyMiwgMjQsIDI2LCA0MiwgNDYsIDYyLCA2NCwgMjI0LCAyMjYsIDI0MiwgMjQ2LCAyNjIsIDI2NCwgNDIyLCA0MjYsIDQ2MiwgNjIyLCA2MjQsIDY0MiwgMjI0NiwgMjI2NCwgMjQyNiwgMjQ2MiwgMjYyNCwgMjY0MiwgNDIyNiwgNDI2MiwgNDYyMiwgNjIyNCwgNjI0MiwgNjQyMlx1Yjg1YyBcdWNkMWQgMzJcdWFjMWNcdWFjZTAsIFx1YzU5OFx1YjEyNFx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NDAgNTE2MjJcdWM1N2MuPFwvcD5cclxuXHJcbjxwPlx1YmI1MFx1ZDU3NC4gXHViZTY4XHViOWFjIFx1YjM1NFx1ZDU3NC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVCAoVCZuYnNwOyZsZTsgNTAwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCA5XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBQPHN1Yj5pPFwvc3ViPiAoMCZuYnNwOyZsZTsgUDxzdWI+aTxcL3N1Yj4gJmxlOyA5KSBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YzgxNVx1YzIxOFx1YjI5NCBpPTF+OVx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMjJiXHVjNzkwIGlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHViYjM4XHVjODFjXHVjNzU4IFx1YjJmNVx1Yzc0NCZuYnNwOzEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzgyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikp1c3QgU3VtIEl0IiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBkaWdpdCBvZiAxIHRvIDksIHN1bSBhbGwgcG9zc2libGUgbnVtYmVycyBnZW5lcmF0ZWQgZnJvbSB0aG9zZSBkaWdpdHMuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLDxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NDAlXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+RGlnaXQ8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjY8XC90ZD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjg8XC90ZD5cclxuXHRcdFx0PHRkPjk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+RnJlcXVlbmN5PFwvdGg+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5JdCBtZWFucyB0aGF0IHdlIGNhbiB1c2UgdXAgdG8gdHdvIGRpZ2l0cyBvZiAyLCBvbmUgZGlnaXQgb2YgNCBhbmQgb25lIGRpZ2l0IG9mIDYuIFRoZXJlIGFyZSBleGFjdGx5IDMyIGRpc3RpbmN0IG51bWJlcnMgdGhhdCBjYW4gYmUgY29uc3RydWN0ZWQgdXNpbmcgdGhlIGFib3ZlIGRpZ2l0czogMiwgNCwgNiwgMjIsIDI0LCAyNiwgNDIsIDQ2LCA2MiwgNjQsIDIyNCwgMjI2LCAyNDIsIDI0NiwgMjYyLCAyNjQsIDQyMiwgNDI2LCA0NjIsIDYyMiwgNjI0LCA2NDIsIDIyNDYsIDIyNjQsIDI0MjYsIDI0NjIsIDI2MjQsIDI2NDIsIDQyMjYsIDQyNjIsIDQ2MjIsIDYyMjQsIDYyNDIsIDY0MjIuIFRoZSBzdW0gb2YgYWxsIHRob3NlIG51bWJlcnMgaXMgNTE2MjIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIFQgKFQgJmxlOyA1MDApIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLiBFYWNoIHRlc3RjYXNlIGNvbnRhaW5zIG5pbmUgaW50ZWdlcnMgUDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IDkpIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgaS10aCBkaWdpdCBmb3IgaSA9IDEuLjkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdGNhc2UsIG91dHB1dCBpbiBhIHNpbmdsZSBsaW5lIHRoZSBzdW0gb2YgYWxsIHBvc3NpYmxlIG51bWJlcnMgZ2VuZXJhdGVkIGZyb20gdGhlIGF2YWlsYWJsZSBkaWdpdHMuIE1vZHVsbyB0aGUgb3V0cHV0IHdpdGggMSwwMDAsMDAwLDAwNy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=