Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

F

By YouKnowWho · Limits 3s, 1.0 GB

You are given an integer sequence $a_1, a_2,\ldots, a_n$.

For any non-negative integer $k$, let $P(k) = \prod\limits_{l \,=\, 1}^{n}{\prod\limits_{\substack{r \,=\, l,\\ MEX(l,\, r) \,=\, k}}^{n}{ F_l ^ {F_r}}}$

Here, $MEX(l, r)$ is the minimum non-negative integer which is not present in the sequence $a_l, a_{l + 1}, \ldots, a_r$ and $F_i$ is the $i^{th}$ Fibonacci number — formally, $F_0 = 1,$ $F_1 = 1$ and $F_i = F_{i - 1} + F_{i - 2}$ for $i \ge 2$. To know more about the $\prod$ notation, smash here.

For each integer $k$ from $0$ to $n$, output $P(k)$ modulo $(10^7+19)$.

Input

The first line of the input contains a single integer $t(1 \le t \le 10^5)$ denoting the number of test cases. The description of $t$ test cases follows.

The first line of each test case contains a single integer $n(1 \le n \le 10^6)$.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n( 0 \le a_i \le n)$.

The sum of $n$ over all test cases does not exceed $10^6$.

Note that there is no subtask in this problem. You will get $100$ points if you can solve it, otherwise $0$.

Output

For each test case, print $n + 1$ lines where for each $k$ from $0$ to $n$, the $(k + 1)^{th}$ line contains one integer — $P(k)$ modulo $(10^7+19)$.

Sample

InputOutput
3
2
0 1
3
2 1 2
5
0 3 0 1 2

4
1
1
864
1
1
1
2295735
216
7776
6561
256
1


In the first test case,

$P(0) = F_2^{F_2} = 2^2 = 4\pmod {10000019}$, as $MEX(2, 2) = 0$,

$P(1) = F_1^{F_1} = 1^1 = 1\pmod {10000019}$, as $MEX(1, 1) = 1$, and

$P(2) = F_1^{F_2} = 1^2 = 1\pmod {10000019}$, as $MEX(1, 2) = 2$.

In the second test case,

$P(0) = F_1^{F_1} \cdot F_1^{F_2} \cdot F_1^{F_3} \cdot F_2^{F_2} \cdot F_2^{F_3} \cdot F_3^{F_3} = 1^1 \cdot 1^2 \cdot 1^3 \cdot 2^2 \cdot 2^3 \cdot 3^3 = 864\pmod {10000019}$, as $MEX(1, 1) = MEX(1, 2) = MEX(1, 3) = MEX(2, 2) = MEX(2, 3) = MEX(3, 3) = 0$,

$P(1) = 1\pmod {10000019}$,

$P(2) = 1\pmod {10000019}$, and

$P(3) = 1\pmod {10000019}$.

In the third test case,

$P(0) = F_2^{F_2} \cdot F_4^{F_4} \cdot F_4^{F_5} \cdot F_5^{F_5} = 2^2 \cdot 5^5 \cdot 5^8 \cdot 8^8 = 2295735\pmod {10000019}$, as $MEX(2, 2) = MEX(4, 4) = MEX(4, 5) = MEX(5, 5) = 0$,

$P(1) = F_1^{F_1} \cdot F_1^{F_2} \cdot F_1^{F_3} \cdot F_2^{F_3} \cdot F_3^{F_3} = 1^1 \cdot 1^2 \cdot 1^3 \cdot 2^3 \cdot 3^3 = 216\pmod {10000019}$, as $MEX(1, 1) = MEX(1, 2) = MEX(1, 3) = MEX(2, 3) = MEX(3, 3) = 1$,

$P(2) = F_1^{F_4} \cdot F_2^{F_4} \cdot F_3^{F_4} = 1^5 \cdot 2^5 \cdot 3^5 = 7776\pmod {10000019}$, as $MEX(1, 4) = MEX(2, 4) = MEX(3, 4) = 2$,

$P(3) = F_3^{F_5} = 3^8 = 6561\pmod {10000019}$, as $MEX(3, 5) = 3$,

$P(4) = F_1^{F_5} \cdot F_2^{F_5} = 1^8 \cdot 2^8 = 256\pmod {10000019}$, as $MEX(1, 5) = MEX(2, 5) = 4$, and

$P(5) = 1\pmod {10000019}$.

Note: If there is no subarray having MEX equal to $k$, then $P(k) = 1$ as $1$ is the multiplicative identity.

Statistics

80% Solution Ratio

Um_nikEarliest, 1M ago

gryffindoFastest, 1.2s

Um_nikLightest, 117 MB

Deshi_TouristShortest, 4088B