Processing math: 100%
Tổng toàn bộ - MarisaOJ: Marisa Online Judge

Tổng toàn bộ

Time limit: 1000 ms
Memory limit: 256 MB

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 T5000 là số lượng test.
  • T dòng tiếp theo mỗi dòng gồm 9 số nguyên 0pi9.

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 109+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