#P0310. 越狱

    传统题 1000ms 256MiB

越狱

题目描述

监狱有连续编号为 11nnnn 个房间,每个房间关押一个犯人。

mm 种宗教,每个犯人可能信仰其中一种。

不存在没有信仰的犯人。

如果相邻房间的犯人信仰的宗教相同,就可能发生越狱。

求有多少种状态可能发生越狱。

输入格式

共一行,包含两个整数 mmnn

输出格式

可能越狱的状态数,对 100003100003 取余。

数据范围

1m108.1 \leq m \leq 10^8.

1n1012.1 \leq n \leq 10^{12}.

输入样例:

2 3

输出样例:

6

样例解释

所有可能的 66 种状态为:(000)(001)(011)(100)(110)(111)(000)(001)(011)(100)(110)(111)

相关

在下列比赛中:

思维题