组合数学经典

第一个人可以信任意m种宗教，后面的每个人只能信m-1种，用快速幂求后面人的情况，最后通过容斥求到答案

答案： $m^n - m\cdot (m - 1)^{n - 1}$

python版本

# 组合数学经典问题
def power(x,p):
    res = 1
    while p > 0 :
        if p & 1:
            res = res*x % mod
        x = x * x %mod
        p >>= 1
    return res

m,n = map(int,input().split())
mod = 100003
print((power(m,n) - m*power((m-1),n - 1) + mod) % mod)