In a certain peach garden, many different seeds are sown, and each seed grows into a peach tree, with no two trees being identical. The peach trees grow and bear fruits according to the following rules:
One day, Sun Wukong, after wandering through the peach garden, decides to steal all the peaches from the trees. The time it takes him to eat all the peaches on a tree is the total time required to traverse all branches between every pair of fruits on the tree (the time to traverse one branch is 1). Calculate the total time it takes for Sun Wukong to eat all the peaches from all the trees in the garden. Print the result modulo p.
(Note: Two peach trees are considered different if the branches on the two trees differ or if the order in which the fruits grow on the trees differs.)
Input
3 6969
Output
24
Input
333 1000000007
Output
121041480
In the first example, there are 6 distinct trees as follows:
The total time required to eat all the peaches from all the trees is 24.