Statistics

Bear Limak loves algorithms and tolerates data structures. Today he learned about the Cartesian tree. You can find a detailed description of this tree at https://en.wikipedia.org/wiki/Cartesian_tree. Below we give a shorter description that is sufficient to solve this problem.

Let A be a sequence of distinct numbers. Each such sequence defines a unique Cartesian tree. The Cartesian tree is determined by the following rules:

1. The Cartesian tree is a rooted binary tree.
2. The nodes of the tree correspond to the elements of A.
3. An in-order traversal of the tree prints the sequence A.
4. The tree is a heap.

A more detailed explanation of the third rule: Consider any node in the tree, and let x be the number in this node. All numbers in the left subtree must appear in A before x, and all numbers in the right subtree must appear in A after x.

A more detailed explanation of the fourth rule: For each node, the number in the node must be strictly smaller than each of the numbers in the children of this node.

Below is a figure that shows the Cartesian tree determined by the sequence A = {9,3,7,1,8,12,10,20,15,18,5}.

We will now define the score of a Cartesian tree. Let T be the Cartesian tree determined by the sequence A. In the tree T there are some nodes that have two children. For each such node, look at the numbers in those two children, find the indices of those two numbers in A, and compute their (positive) difference. The score of the tree T is the sum of all these differences.

For example, in the above tree we have four nodes that have two children each: the nodes with numbers 1, 3, 10, and 15. The children of node 1 are the nodes 3 and 5. In the original sequence A, the values 3 and 5 have (0-based) indices 1 and 10. The difference between these indices is 10 - 1 = 9. For the other three nodes with two children, the differences between their indices are 2, 3, and 2. Hence, the score of this tree is 9 + 2 + 3 + 2 = 16.

You are given the ints N and MOD. There are N! permutations of the numbers 1 through N. Each of these permutations determines a Cartesian tree. Let X be the sum of the scores of these N! trees. Compute and return the value (X modulo MOD).