以下の式は今回の問題を解くにあたっての重要な等式である.

\[\sum_{\substack{1 \leq i \leq M \\ 1 \leq j \leq N}} A_i B_j =\left( \sum_{i=1}^M A_i \right) \left( \sum_{j=1}^N B_j\right)\]

この等式を参考にすると, \(S\) は

\[S=\sum_{\substack{1 \leq i_k \leq 6 \\ k=1, \dots, N}} (A_{1,i_1} \times \dots \times A_{N,i_N})=\left( \sum_{i_1=1}^6 A_{1,i_1} \right) \times \dots \times \left( \sum_{i_N=1}^6 A_{N,i_N} \right)\]

となり, 各サイコロの目の総和の積が \(S\) と一致することがわかる.

このことから, \(S \pmod{(10^9+7)}\) を \(O(N)\) で求めることができる.