F

Let $M = 10^7 + 19$.

First things first, let $g=6$ be the primitive root of $M$(Primitive roots can be calculated in $\mathcal{O}(\sqrt{M})$). So by definition, we can express any number $\neq 0$ using some power of $g$ under modulo $M$. Let, $F_i \equiv g^{G_i} \pmod{M}$. Notice that, for the given mod, $M$, there is no such value $k \le 10^6$ s.t. $F_k \equiv 0 \, (\textrm{mod}\ M)$. So we don't have to worry about dealing with zeroes. All $G_i$ for $0 < i < M$ can be calculated in $\mathcal{O}(M)$.

Now, $F_l^{F_r} \equiv g^{G_l \cdot F_r}\pmod M$.

So our equation becomes $P(k) \equiv \prod\limits_{l \,=\, 1}^{n}{\prod\limits_{\substack{r \,=\, l,\\ MEX(l,\, r) \,=\, k}}^{n}{ g^{G_l \cdot F_r}}}\pmod M$

or, $P(k) \equiv g^{\sum\limits_{l \,=\, 1}^{n}{\sum\limits_{\substack{r \,=\, l,\\ MEX(l,\, r) \,=\, k}}^{n}{G_l \cdot F_r}}} \pmod M$

So we have to compute the sum of the products ${G_l \cdot F_r}$.

Let $ans_k = \sum\limits_{i = k}^{n}{P(k)}$. We will compute $ans_k$ for each $k$ from $0$ to $n$.

Build an array $left$ where $left_r$ is the maximum index $\leq r$ such that for each index $l \le left_r$, MEX of the subarray $[l, r]$ is $\ge k$.

Now, let's build the array $left$ for each $k$ from $0$ to $n$ in order. To generate the array for $k + 1$, update the array $left$ using the occurrences of $k$ in $a$. For that we have to perform:

• range updates like set $left_i = \min(left_i, x): L\le i \le R$ for some range $(L, R)$ and some integer $x$.

• range queries like sum of $F_i \cdot (G_1 + G_2 + \dots + G_{left_i}): 1 \le i \le n$.

We can solve this part using Segment Tree Beats. Please see the setter’s solution for more clarity.

One can also observe that $left$ is a non-decreasing array. So the operations can also be done using a normal segment tree.

Overall Complexity: $\mathcal{O}(n \, log(n) + M)$.

Setters solution: smash here .