@[Vin\_1999](/space/show?uid=17378)
抱歉现在才看到这个问题。
事实上，$\frac{M+1}{2}$就是$2$对于$M$的逆元。
证明很简单，$\frac{M+1}{2}*2\equiv M+1\equiv1\mod M$
但是这里为了保证答案不爆long long而采用了保险而复杂的计算，
所以是乘上了```((M+1)/2%M)%M```
事实上只要```(M+1)/2%M```应该就行了www
by Scarlet @ 2016-11-03 18:15:07
@[Scarlet](/space/show?uid=829) 谢谢红字，君？！
by Vin_1999 @ 2016-11-03 18:39:23
0.
by marshal王子祥 @ 2018-01-15 21:56:06