有一天66檸檬66不幸追撞了肯肯肯的豐田世紀，肯肯肯很生氣，給66檸檬66看了以下的 C++ 程式碼：

這個是合併排序的程式，輸入陣列大小 $n$ 與一個 $1\sim n$ 的排列 $a_1\sim a_n$，程式會將 $a_1\sim a_n$ 排序好，並輸出呼叫 cmp 函式的次數 cnt。

肯肯肯給66檸檬66的和解條件是：輸入 $n,p$，$p$ 為質數，66檸檬66要輸出對於所有 $1\leq k\leq n$，大小為 $k$ 的排列經過以上程式的 merge_sort 後，cnt 的期望值是多少。

答案要 $\text{mod }p$ 後再輸出，若答案為 $x$，並且化成最簡分數後為 $\frac{a}{b}$，那 $x\text{ mod }p=a\times b^{-1}\text{ mod }p$，其中 $b^{-1}$ 為 $b$ 的模逆元。

66檸檬66想了三回後還是沒想到，請你幫幫他！