bzoj1008: [HNOI2008]越狱

Description

监狱有连续编号为 1...... N 的 N 个房间, 每个房间关押一个犯人, 有 M 种宗教, 每个犯人可能信仰其中一种. 如果 相邻房间的犯人的宗教相同, 就可能发生越狱, 求有多少种状态可能发生越狱

Input

输入两个整数 M, N. 1<=M<=10^{8, 1<=N<=10}12

Output

可能越狱的状态数, 模 100003 取余

Sample Input

2 3

Sample Output

6

HINT

6 种状态为 (000) (001) (011) (100) (110) (111)

Source

巨水快速幂, 但是有一件事要考虑到, 就是 C++在计算模的时候会忽视所有负数, 所以所有负数在模之前都要尽可能地保证值大于 (等于) 零.

结论:res = n ^ m - m * (n - 1) ^ (m - 1)

就是说总共有 n ^ m 种方法排列, 但是对于第一个人的 m 种排列方法来说, 后面的 n - 1 个人就只有 (n - 1) ^ (m - 1) 种排法, 综上就是那个答案.

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

int main(int argc, char** argv)
{
    return 0;
}

from pydatagen import *
printf('%d %d\n' % (randint(1, 100000000), randint(1, 1000000000000)))
fclose()