問題文

N 個の 6 面体サイコロがあり、1, 2, 3, \cdots, N と番号付けられています。 サイコロ i の j (1 \leq j \leq 6) 番目の面には整数 A_{i,j} が書かれています。ここで、それぞれのサイコロについて、書かれている整数は相異なります。

さて、サイコロの出目に対して、次のように得点を定義します。

得点は N 個のサイコロの出目の総積である。 つまり、サイコロ i の出目を R_i としたとき、得点は R_1 \times R_2 \times \dots \times R_N と計算される。

N 個のサイコロの出目の結果としては 6^N 通り考えられますが、これら全てにおける得点の総和 S を 10^9 + 7 で割った余りを求めてください。ただし、それぞれのサイコロは互いに区別できるものとします。

制約

• 1 \leq N \leq 100
• 1 \leq A_{i,1} < A_{i,2} < A_{i,3} < A_{i,4} < A_{i,5} < A_{i,6} \leq 100
• 入力はすべて整数である

入力例 1

2
1 2 3 5 7 11
4 6 8 9 10 12

出力例 1

1421

例えば、出目が 3, 10 だった場合の得点は 3 \times 10=30 より、 30 です。サイコロの出目の結果は 6^2=36 通り考えられ、全ての得点の総和は 1421 です。

入力例 2

1
11 13 17 19 23 29

出力例 2

112

サイコロが 1 つだけの場合の答えは、唯一のサイコロの各面に書かれている整数の総和になります。

入力例 3

7
19 23 51 59 91 99
15 45 56 65 69 94
7 11 16 34 59 95
27 30 40 43 83 85
19 23 25 27 45 99
27 48 52 53 60 81
21 36 49 72 82 84

出力例 3

670838273

S=211411531150718976 ですが、出力すべき答えは S を 10^9+7 で割った余りである 670838273 であることに注意してください。