29150번 - 기초적인 문제

행렬식은 선형대수학에서 다루는 기초적인 대상 중 하나이다. 이항계수는 조합론에서 다루는 기초적인 대상 중 하나이다.

두 기초적인 대상을 섞은 문제는 기초적이므로, 다음 행렬의 행렬식을 구하는 문제는 기초적인 문제이다.

$$A(a_1,a_2,\cdots,a_N)=\left({a_i\choose {j-1}}\right)_{i,j}=\begin{pmatrix}{a_1\choose 0}&{a_1\choose 1}&\cdots&{a_1\choose N-1}\\{a_2\choose 0}&{a_2\choose 1}&\cdots&{a_2\choose N-1}\\\vdots&\vdots&\ddots&\vdots\\{a_N\choose 0}&{a_N\choose 1}&\cdots&{a_N\choose N-1}\end{pmatrix}$$

단, ${N\choose{K}}=\left\{\begin{matrix}\frac{N!}{K!(N-K)!}&(N\ge K)\\0&(N<K)\end{matrix}\right.$는 이항계수이다.

기초적인 문제는 쉽게 풀 수 있으므로, 쿼리마다 정수 $a_1,a_2,\cdots,a_N$이 주어지면 위 행렬의 행렬식을 구해보도록 하자.

첫 번째 줄에 쿼리의 수 $Q$가 주어진다. $(1 \le Q \le 200)$

두 번째 줄부터 $2Q$개의 줄에 걸쳐 쿼리에 대한 정보가 주어진다.

각 쿼리는 두 줄로 이루어져 있다. 쿼리의 첫 번째 줄에는 행렬의 크기 $N$이 주어지며, 두 번째 줄에는 $N$개의 음이 아닌 정수 $a_1,a_2,\cdots,a_N$이 공백으로 구분되어 주어진다. $(1\le N\le 500;$ $0\le a_i<1\,000\,000\,007)$

한 줄에 하나씩 순서대로 $\det A(a_1,a_2,\cdots,a_N)$을 $1\,000\,000\,007(=10^9+7)$로 나눈 나머지를 출력한다. 정확하게는, $\det A(a_1,a_2,\cdots,a_N)\equiv M\pmod{1\,000\,000\,007}$인 정수 $M$을 출력한다. $(0\le M<1\,000\,000\,007)$

단, $1\,000\,000\,007$은 소수이다.