Sutomo 1 P2S1 Programming Contest

Informally, a permutation of a set of objects is an arrangement of those objects into a particular order. For example, there are six permutations of the set {1,2,3}, namely (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). The number of permutations of N distinct objects or numbers is N * (N-1) * (N-2) * ... * 2 * 1 = N!. In this problem, given a non-negative integer N that indicates N distinct objects numbered from 1 to N and the K-th permutation of N objects, find the integer K.

Input

The input consists of an integer N(1 <= N <= 20) in the first line, followed by the K-th permutation of N objects in the next line.

Output

A non-negative integer K in single line. Note that K may be too big for longint, use int64 instead.

Example

Input 1:
3
3 2 1

Output 1:
6

Input 2:
5
5 4 2 1 3

Output 2:
117

Penjelasan

The set {1, 2, 3} has six permutations. The first permutation is itself (1, 2, 3), followed by (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1) are the second, third, fourth, fifth and the sixth permutation respectively.

The set {1, 2, 3, 4, 5} has a hundred and twenty permutations.