解题思路
道路是一个长为 N、宽为 M 的矩形，需要用 1×1 和 2×2 的砖铺满。
因为 M≤5 很小，而 N 很大，所以不能直接按 N 做普通动态规划。可以使用状态压缩动态规划 + 矩阵快速幂。
按列从左到右铺路。
用一个 M 位二进制状态 mask 表示当前列中哪些位置已经被上一列放出的 2×2 砖占用。
P4961.第4题-多多的道路修建Ⅱ
题目内容
多多现在在负责多多乡村的修建。
道路修建问题可以看作是在一条直线上，有N个单位。
经过认真分析，他发现每一段路有两种修建的方案，分别为“修1”和“修2”。
多多规定，一段有两种方案的路，可以把道路的空间给完全铺掉。
注意：石块不能拆分（会影响美观），以及石块之间不可重叠（道路会凹凸不平）。
输入描述
共一行，两个正整数N和M，分别表示要修建的道路的长度。
(1≤N≤1,000,000,000,1≤M=14=5)
输出描述
输出一个整数，表示不同修建方案的数量。
由于答案可能会很大，只需要输出答案对 1,000,000,007 取模后的值即可。
补充说明
对于80%的数据，1≤N≤100000
对于100%的数据，有1≤N≤1000000000
样例1
输入
4 2
输出
5
说明
以字符 O 表示 1∗1 的石砖，字符 X 表示 2∗2 的石砖的 1/4，满足修建的方案有：
(1)
OOOO
OOOO
(2)
XXOO
XXOO
(3)
OXXO
OXXO
(4)
OOXX
OOXX
(5)
XXXX
XXXX
样例2
输入
3 3
输出
5
样例3
输入
2 5
输出
8
