#P16722. liangxing

liangxing

题目描述

令 fnf_n 为满足以下条件的 nn 的排列 pp 的个数:

  1. 对所有 1≤i<n1\le i<n,均有

    ∣pi−pi+1∣≤3;|p_i-p_{i+1}|\le 3;
  2. p1=1p_1=1,pn=np_n=n。

给定 n,mn,m,求

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

输入格式

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

输出格式

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

样例输入

10 3

样例输出

18230635

数据范围与约定

n≤1018,1≤m≤3。n\le 10^{18},\qquad 1\le m\le 3。
子任务 分值 特殊限制
1 10 n≤10n\le 10
2 20 n≤105n\le 10^5
3 m≤2m\le 2
4 n≤109n\le 10^9
5 30 无特殊限制