Problem 1041 --数论编程-垒骰子

1041: 数论编程-垒骰子

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board][Creator:]

Description

Input

第一行两个整数 n m
n表示骰子数目
接下来 m 行,每行两个整数 a b ,表示 a 和 b 数字不能紧贴在一起。

Output

一行一个数,表示答案模 10^9 + 7 的结果。

Sample Input

2 1
1 2

Sample Output

544

HINT


本题当数很大时如果用线性动态规划会超时,需要使用矩阵快速幂进行优化



blog./lonverce/article/details/45169285

Source

[Submit][Status]