F

YouKnowWho

National High School Prog...

7/9/33

Statement Editorial Statistics Discussion

HTML

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

Input	Output
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}$ .

Input

Output

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.

Factors

	CPU	Memory	Source
Bash 5.2	1×	1×	1×
Brainf*ck	1×	1×	1×
C# Mono 6.0	1×	1×	1×
C++17 GCC 13.2	1×	1×	1×
C++20 Clang 16.0	1×	1×	1×
C++20 GCC 13.2	1×	1×	1×
C++23 GCC 13.2	1×	1×	1×
C11 GCC 13.2	1×	1×	1×
C17 GCC 13.2	1×	1×	1×
C23 GCC 13.2	1×	1×	1×
Common Lisp SBCL 2.0	1×	1×	1×
D8 11.8	1×	1×	1×
Erlang 22.3	1×	1×	1×
Free Pascal 3.0	1×	1×	1×
Go 1.22	1×	1×	1×
Grep 3.7	1×	1×	1×
Haskell 8.6	1×	1×	1×
Java 1.8	1×	1×	1×
Kotlin 1.1	1×	1×	1×
Lua 5.4	1×	1×	1×
Node.js 10.16	1×	1×	1×
Perl 5.30	1×	1×	1×
PHP 8.3	1×	1×	1×
PyPy 7.1 (3.6)	2×	2×	1×
Python 3.12	1×	1×	1×
Ruby 3.2	1×	1×	1×
Rust 1.57	1×	1×	1×
Swift 5.3	1×	1×	1×
Whitespace	1×	1×	1×

uDebug

Submit

Statistics

78% Solution Ratio

Um_nikEarliest, Jun '21

user.794723Fastest, 1.0s

nusuBotLightest, 108 MB

Deshi_TouristShortest, 4088B