題目 2516:
信息學奧賽一本通T1618-越獄
時間限制: 2s
內存限制: 192MB 提交: 163 解決: 45
題目描述
原題來自：HNOI 2008
監(jiān)獄有連續(xù)編號為 1 到 n 的 n 個房間，每個房間關押一個犯人。有 m 種宗教，每個犯人可能信仰其中一種。如果相鄰房間的犯人信仰的宗教相同，就可能發(fā)生越獄。求有多少種狀態(tài)可能發(fā)生越獄。
輸出格式
可能越獄的狀態(tài)數(shù)，對 100003 取余。
提示
樣例說明
所有可能的 6 種狀態(tài)為：{0,0,0},{0,0,1},{0,1,1},{1,0,0},{1,1,0},{1,1,1}。
數(shù)據(jù)范圍與提示：
對于全部數(shù)據(jù)，1≤m≤108,1≤n≤1012 。