This page is still under construction.

Parts of this page are still being built. What you see may change.

Arrange and Count!

Time limit5sMemory limit512 MB

Summary
Given a sequence, count modulo 1e9+7 how many distinct orderings the prefix-reversal-then-append operation can produce, over multiple test cases.
Level

Hard8 of 10

Topics
Combinatorics, Math, Implementation, Brute force
Solved
No attempts yet

Problem

Alice has a sequence a1,a2,…,ana_1,a_2,\dots,a_n. She can rearrange the sequence using the following operation any number of times:

  • Select an integer ii (1≤i≤n1 \le i \le n) and change the sequence to ai,ai−1,…,a1,an,an−1,…,ai+1a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}.

Alice wants to know how many different sequences can be obtained, modulo (109+7)(10^9+7).

Input

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains an integer nn, the length of the sequence.

The second line contains nn integers a1,a2,…,ana_1, a_2, \dots, a_n.

Output

For each test case, print an integer which denotes the result.

Constraints

  • 1≤n≤1051 \leq n \leq 10^5
  • 1≤ai≤n1 \leq a_i \leq n
  • The sum of nn does not exceed 2×1062 \times 10^6.

Examples1

  1. Example 1

    Input
    4
1 1 1 1
4
1 1 2 2
4
1 2 1 2
4
2 1 2 1
    Expected output
    1
4
2
2