liangxing - 题目详情 - https://new.bzoj.org:88

ID: 15932

传统题

3000ms

1024MiB

难度: 9

上传者:

标签>

CF2600

计数DP

矩阵

动态规划

题目描述

令 $f_n$ 为满足以下条件的 $n$ 的排列 $p$ 的个数：

对所有 $1\le i<n$ ，均有
$|p_i-p_{i+1}|\le 3；$
$p_1=1$ ， $p_n=n$ 。

给定 $n,m$ ，求

\sum_{i=1}^{n} f_i^m \bmod (10^9+7)。

输入格式

一行两个整数 $n,m$ 。

输出格式

输出一个整数，表示答案。

样例输入

10 3

样例输出

18230635

数据范围与约定

n\le 10^{18},\qquad 1\le m\le 3。

子任务	分值	特殊限制
1	10	$n\le 10$
2	20	$n\le 10^5$
3		$m\le 2$
4		$n\le 10^9$
5	30	无特殊限制