409187: GYM103451 G Krosh and permutation and expected number
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
G. Krosh and permutation and expected numbertime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
You are given number $$$n$$$. Consider permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$. Define $$$f(l, r) = (((p(l)$$$ $$$mod$$$ $$$p(l + 1))$$$ $$$mod$$$ $$$p(l + 2))$$$ $$$mod$$$ ... $$$mod$$$ $$$p(r)$$$. Let's beauty of permutation $$$B(p)$$$be the sum $$$f(l, r)$$$ over all the subsegments of permutation $$$B(p) = \sum_{l = 1}^n \sum_{r = l}^n f(l, r)$$$. Find expectation of the beauty of randomly chosen permutation of $$$n$$$ integers over given prime modulo $$$m$$$. It can be shown that answer can be represented as fraction $$$\frac{P}{Q}$$$, where $$$P$$$, $$$Q$$$ are integers and $$$Q \neq 0$$$ $$$(mod$$$ $$$m)$$$.
InputYou are given numbers $$$1 \le n \le 300$$$ and $$$10^8 \le m \le 10^9$$$ where m is prime.
OutputOutput answer.
ExamplesInput2 998244353Output
499122180Input
1 998244353Output
1Input
3 700000001Output
8