Grenade throws from Valera#12198

Grenade throws from Valera

2 seconds

1,024 megabytes

Hard

Valera learned another connector smoke, but out of habit, he threw a molotov at his teammates' feet instead. Now, to get invited to FaceIt again, he needs to solve the problem of a person who plays CS2 on macOS. However, he needs to keep learning smokes, so he asked you to help him with the problem.

Given an array $a$ of length $n$ . You need to find the number of ways to split it into contiguous subarrays such that the $m e x$ of the $i$ -th subarray is equal to $i - 1$ i−1. Here $i$ is in $1$ -indexation. Because of the loss of Problem Setter's favorite CS2 team, he asks you to calculate this modulo $1 0^{9} + 7$ 10^9+7.

The mex (minimum excluded value) of a set of non-negative integers is the smallest non-negative integer that is not present in the set. The mex of ${1, 0, 2, 4}$ \{1,0,2,4\} is $3$ . The mex of ${1, 2, 3}$ \{1,2,3\} is $0$ . The mex of ${0, 2, 3}$ \{0,2,3\} is $1$ .

Input

The first line contains one integer $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \leq n \leq 2 \cdot 10^5) — the size of array $a$ .

The second line contains $n$ integers $a_{i}$ a_i ( $0 \leq a_{i} < n$ 0 \leq a_i < n) representing the elements of the array $a$ .

Output

For each test case, output a single integer — the number of ways to split the array into contiguous subarrays such that the condition described in the statement is satisfied, modulo $1 0^{9} + 7$ 10^9 + 7.

Examples

Example 1

Loading

Scoring

( $14$ points): $n \leq 20$ n \le 20
( $14$ points): $n \leq 100$ n \le 100;
( $16$ points): $n \leq 500$ n \le 500;
( $28$ points): $n \leq 800$ n \le 800;
( $60$ points): $n \leq 5 \cdot 1 0^{4}$ n \le 5\cdot10^4;
( $40$ points): $n \leq 1 0^{5}$ n \le 10^5;
( $28$ points): no additional constraints

i - 1

1 0^{9} + 7

{1, 0, 2, 4}

{1, 2, 3}

{0, 2, 3}

1 \leq n \leq 2 \cdot 1 0^{5}

a_{i}

0 \leq a_{i} < n

1 0^{9} + 7

n \leq 20

n \leq 100

n \leq 500

n \leq 800

n \leq 5 \cdot 1 0^{4}

n \leq 1 0^{5}