1767 . Ch3. Section 2. 墜落
Description
儘管破壞了最強的能量流動，
可是仍難免會有崩壞的產生。
妁艷與楓音就這樣掉到了地底下，圖書館的地底下...
圖書館的地底下？妁艷怎麼都不知道有這個地方...
只見這地方十分陰暗，兩排的棺材...讓妁艷感到不寒而慄..
不知道該如何是好...
慢慢地往前，他發現了前方的石門，不知道該如何再往前...
這時只聽見楓音說著「旁邊的...棺材...」
妁艷很緊張的往旁邊看，發現棺材已經跳出一隻不知名生物了!!!
那不明物體還向妁艷挑釁"Let's battle!!!"
結果妁艷不小心(?)回錯話了"Let's tetris battle!!!"......
忽然妁艷發現那棺材上有5*4的方格，好像可以放東西
妁艷就從它的包包內拿出了無數的七彩方塊
當然這些方塊你要有幾個妁艷就有幾個，而且都是可以旋轉的
當妁艷拿出其中五個擺到棺材上時
突然間棺材就發亮了，那敵人似乎就被收服回去了。
可是，不久後又有好多棺材都跑出敵人了，而且每個棺材的長度不一樣，
好在棺材寬度都是5，也就是說大小是5*n
還有，雖然有可能有同樣長度的棺材，不過同一種擺法用第二遍好像就沒有用了......
所以現在妁艷想知道的是，給你一個長度n寬度5的矩形，還有很多很多上面那七種方塊，
總共有幾種方法能填滿這矩形呢?
(鏡像、旋轉，都算不同的擺法，因為敵人認不太出來...)
Input Format
輸入包含多筆測資
每行會有兩個數字n和m(1≤n≤1000 , 1≤m≤1000000007)
n就是棺材的長度
因為答案會太大所以要mod m
Output Format
對於每筆測資各輸出一行答案
輸出 解法數 mod m 即可
Sample Input 1
Sample Output 1
Hints
妁艷看著眼前的敵人，感到十分的力不從心。
從控制室的剛彈(?)、樓上的魔法漿、到現在，不斷的消耗著體力，妁艷還可以戰鬥，不過已經沒有先前如此的靈敏了。
依據眼前敵人出現的方式判斷，之後想必還會有很多的敵人。而十分不妙的是，在這種情況下妁艷無法進行補魔力的動作。
為了讓妁艷可以繼續戰鬥，楓音決定和妁艷合體，以獲得更強大的能量。
Problem Source
原TIOJ1767 / problem setter: lnsuyn
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 25 |
| 2 | 1 | 25 |
| 3 | 2 | 25 |
| 4 | 3 | 25 |