TopCoder

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

60.0% (3/5)

Tags

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

4 1000

Sample Output

454

Hints

妁艷看著眼前的敵人,感到十分的力不從心。

從控制室的剛彈(?)、樓上的魔法漿、到現在,不斷的消耗著體力,妁艷還可以戰鬥,不過已經沒有先前如此的靈敏了。

依據眼前敵人出現的方式判斷,之後想必還會有很多的敵人。而十分不妙的是,在這種情況下妁艷無法進行補魔力的動作。

為了讓妁艷可以繼續戰鬥,楓音決定和妁艷合體,以獲得更強大的能量。

Problem Source

原TIOJ1767 / problem setter: lnsuyn

Subtasks

No. Testdata Range Score
1 0 25
2 1 25
3 2 25
4 3 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4