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 a1,a2,,ana_1, a_2,\ldots, a_n.

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

Here, MEX(l,r)MEX(l, r) is the minimum non-negative integer which is not present in the sequence al,al+1,,ara_l, a_{l + 1}, \ldots, a_r and FiF_i is the ithi^{th} Fibonacci number — formally, F0=1,F_0 = 1, F1=1F_1 = 1 and Fi=Fi1+Fi2F_i = F_{i - 1} + F_{i - 2} for i2i \ge 2. To know more about the \prod notation, smash here.

For each integer kk from 00 to nn, output P(k)P(k) modulo (107+19)(10^7+19).

Input

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

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

The second line contains nn space-separated integers a1,a2,,an(0ain)a_1, a_2, \ldots, a_n( 0 \le a_i \le n).

The sum of nn over all test cases does not exceed 10610^6.

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

Output

For each test case, print n+1n + 1 lines where for each kk from 00 to nn, the (k+1)th(k + 1)^{th} line contains one integer — P(k)P(k) modulo (107+19)(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)=F2F2=22=4(mod10000019)P(0) = F_2^{F_2} = 2^2 = 4\pmod {10000019}, as MEX(2,2)=0MEX(2, 2) = 0,

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

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

In the second test case,

P(0)=F1F1F1F2F1F3F2F2F2F3F3F3=111213222333=864(mod10000019)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)=0MEX(1, 1) = MEX(1, 2) = MEX(1, 3) = MEX(2, 2) = MEX(2, 3) = MEX(3, 3) = 0,

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

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

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

In the third test case,

P(0)=F2F2F4F4F4F5F5F5=22555888=2295735(mod10000019)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)=0MEX(2, 2) = MEX(4, 4) = MEX(4, 5) = MEX(5, 5) = 0,

P(1)=F1F1F1F2F1F3F2F3F3F3=1112132333=216(mod10000019)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)=1MEX(1, 1) = MEX(1, 2) = MEX(1, 3) = MEX(2, 3) = MEX(3, 3) = 1,

P(2)=F1F4F2F4F3F4=152535=7776(mod10000019)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)=2MEX(1, 4) = MEX(2, 4) = MEX(3, 4) = 2,

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

P(4)=F1F5F2F5=1828=256(mod10000019)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)=4MEX(1, 5) = MEX(2, 5) = 4, and

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


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

    Discussion

    Statistics


    80% Solution Ratio

    Um_nikEarliest, 1M ago

    gryffindoFastest, 1.2s

    Um_nikLightest, 117 MB

    Deshi_TouristShortest, 4088B

    Submit

    Login to submit

    Editorial

    Let M=107+19M = 10^7 + 19M=107+19. First things first, let g=6g=6g=6 be the primitive root of MMM(Pr...