Cô giáo làng Kamishirasawa Keine nhặt được một cuốn sách lạ, hóa ra đó là sách dạy lập trình ở thế giới bên ngoài. Cô định mang về dạy cho các bạn nhỏ nhưng vì sách toàn bài tập khó nên cả cô vẫn chưa giải được. Chính vì thế cô nhờ bạn giúp giải bài toán sau:

Với mỗi số từ ~1~ đến ~9~ cho ~p_i~ là số lần xuất hiện của chữ số ~i~. Hãy tính tổng của tất cả các số khác nhau được tạo bởi những chữ số đã cho.

Input

• Dòng đầu tiên là số nguyên dương ~T \le 5000~ là số lượng test.
• ~T~ dòng tiếp theo mỗi dòng gồm 9 số nguyên ~0 \le p_i \le 9~.

Output:

• ~T~ dòng mỗi dòng là một số nguyên duy nhất là tổng các số có thể tạo được modulo ~10^9+7~.

Sample Test

Input:

3
0 0 0 1 0 0 0 1 0
0 0 0 1 0 1 0 2 0
1 2 0 2 1 1 1 0 1 

Output:

144
95818
689045052

• Giải thích: Ở test đầu tiên các số tạo ra được là: ~4 + 8 + 48 + 84 = 144~