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 pi 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 ≤ 5000 là số lượng test.

• T dòng tiếp theo môi dòng gồm 9 số nguyên 0 ≤ pi ≤ 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.

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