[排队]
题目描述
老师带着 n 名学生前往小码博物馆参观,由于小码博物馆的的道路比较窄,现在老师让大家排成一列前去参观,每一个学生都一个兴趣爱好,一共有m 种。如果相邻的学生的兴趣爱好相同,就可能发生交头接耳,求有多少种状态可能发生交头接耳。
注意:学生已经排好序列,不需要重新安排顺序
答案对 100,003 取模。
提示
对于 100% 的数据,保证 1≤m≤10
8
,1≤n≤10
12
。
输入格式
输入只有一行两个整数,分别代表兴趣爱好数 m 和学生数 n。
输出格式
输出一行一个整数代表答案。
样例组
输入#1
输出#1
2 3
6