Alice 有一个序列 $a_1, a_2, \dots, a_n$。她可以对该序列进行任意次数的以下操作：
- 选择一个整数 $i$ ($1 \le i \le n$)，将序列变为 $a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}$。
Alice 想知道可以得到多少种不同的序列，结果对 $(10^9 + 7)$ 取模。
输入格式
输入包含多个测试用例，以文件结束符（EOF）终止。对于每个测试用例：
第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。
- $1 \le n \le 10^5$
- $1 \le a_i \le n$
- 所有测试用例的 $n$ 之和不超过 $2 \times 10^6$。
输出格式
对于每个测试用例，输出一个整数，表示结果。
样例
样例输入 1
4 1 1 1 1 4 1 1 2 2 4 1 2 1 2 4 2 1 2 1
样例输出 1
1 4 2 2