P14109

核电站

难度 4 级小学算法入门倍增递推矩阵

讨论统计 9通过 22提交 40.9%通过率旧版界面

时间限制 1 秒 内存限制 64 MB

题目描述

一个核电站有 $n$ 个放核物质的坑，排列在一条直线上。每个坑可以选择放或者不放置核物质，如果连续 $m$ 个坑中放入核物质就会发生爆炸，所以某些坑中就不能放核物质。

本题的任务是：对于给定的 $n$ 和 $m$ ，求不发生爆炸的放置核物质的方案总数。

一行两个正整数 $n$ 和 $m$ ，之间用一个空格隔开， $2≤n≤10^{18}，2≤m≤100$ 。

一行一个正整数，表示方案总数,结果对 $10^9+7$ 取模。

样例 1

输入

4 3

输出

课课通

上一题下一题