传送门= ̄ω ̄=

思路

排列组合……首先我们可以算出不能越狱有多少种情况:第一个房间有m种可能(宗教),第二个房间因为不可以发生越狱,所以不能和第一个房间一样,所以是有(m-1)种可能,第三个房间同理,也是(m-1)种可能,以此类推。所以不能越狱共有:m×(m-1)^(n-1) 种可能。而总共有m^n种可能,所以最终答案为m^n-m×(m-1)^(n-1) 。

所以很明显,用快速幂就行了,记得取膜。最后做减法可能会减出负数,所以要把答案加上100003再取膜。

还有!要开long long!

代码