Description

AA has a sequence of a[1..n], which is an arrangement of 1, 2, ..., n. AA wants to make some transformations on this sequence: each time he can choose a pair of i, j, satisfy 1 ≤ i < j ≤ n and a[i] > a[j], then a[i] and a[j] Exchange. If an array b[1..n] can be obtained from the initial series a several times, then we say that b is reachable. Now AA wants to know how many different sorts of reach can be reached. Since the answer may be very large, you only need to output the result after the answer module 1e9+7.

Format

Input

There are multiple test cases.For each case, The first line is an integer n. (1 ≤ n ≤ 20)The next line is a space separated by n integers, a[1], a[2], ..., a[n], to ensure that it is an n-arrangement.

Output

For each test cases, Outputs the result of one line of the answer to mode 1e9+7.

Samples

4
2 4 1 3

8

Hint