Heavenly Peach Garden - MarisaOJ: Marisa Online Judge

Heavenly Peach Garden

Time limit: 1000 ms
Memory limit: 256 MB
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: - Each tree will consist of exactly $n$ fruits and $n-1$ branches, initially having only one fruit. - At each step, the peach tree can grow a fruit on one of the two branches from an existing fruit. (Each fruit can have at most 2 branches beneath it.) - Once all the trees have grown $n$ fruits, they stop, and the configurations of all these trees are distinct. 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 - Contains two positive integers, $n$ and $p$. ### Output - Print the result of the calculation modulo $p$. ### Constraints - $n \leq 2000$. - $p \leq 10^9 + 7$. ### Example Input ``` 3 6969 ``` Output ``` 24 ``` Input ``` 333 1000000007 ``` Output ``` 121041480 ``` ### Explanation 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.