E. Non-adjacent Swaps
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a permutation. In one step, you can swap any two adjacent elements if their values differ by more than one.

Consider all permutations that can be obtained using these operations, starting from a given permutation. Define a distance between two permutations as the minimum number of these operations required to transform the first permutation into the second one.

Find the number of permutations that can be obtained and the sum of distances to all those permutations from the starting one.

Input

The first line contains the integer $$$n$$$ ($$$1 \le n \le 100$$$) — the permutation size. The second line contains $$$n$$$ distinct integers $$$a_i$$$ ($$$1 \le a_i \le n$$$) — the starting permutation.

Output

Output two integers, the number of obtainable permutations, and the sum of distances to those permutations. Calculate both numbers modulo $$$1\,000\,000\,007$$$.

Scoring
SubtaskPointsConstraints
115$$$n \le 8$$$
220$$$n \le 15$$$
330$$$n \le 30$$$
420$$$n \le 50$$$
515No additional constraints
Examples
Input
4
3 1 4 2
Output
5 5
Input
5
1 2 3 4 5
Output
1 0
Input
6
5 3 1 2 4 6
Output
61 218
Note

In the first example, you can obtain the following permutations:

  • $$$\lbrack 3, 1, 4, 2 \rbrack$$$, in 0 steps;
  • $$$\lbrack 3, 1, 2, 4 \rbrack$$$, in 1 step;
  • $$$\lbrack 1, 3, 4, 2 \rbrack$$$, in 1 step;
  • $$$\lbrack 3, 4, 1, 2 \rbrack$$$, in 1 step;
  • $$$\lbrack 1, 3, 2, 4 \rbrack$$$, in 2 steps (swap two pairs of elements with values $$$(3, 1)$$$ and $$$(4, 2)$$$).

There are five permutations in total; the sum of distances also equals five.

In the second example, you can't perform any swap, so only one permutation is reachable with a distance of 0.