Neko Rules the Catniverse (Large Version)

给定参数 $n,k,m$，你需要求有多少个大小为 $k$ 的序列 $a$ 满足如下三个条件： 1. 任意两个元素其权值不同。 2. 对于任意 $i$ 满足 $1\le i\le k$ 有 $1\le a_i\le n$。 3. 对于任意 $i$ 满足 $2\le i\le k$ 有 $a_i\le a_{i-1}+m$。 答案对 $10^9+7$ 取模。 数据范围： $1\le n\le 10^9$，$1\le k\le \min(n,12)$，$1\le m\le 4$。 translated by Soulist

This problem is same as the previous one, but has larger constraints. Aki is playing a new video game. In the video game, he will control Neko, the giant cat, to fly between planets in the Catniverse. There are $ n $ planets in the Catniverse, numbered from $ 1 $ to $ n $ . At the beginning of the game, Aki chooses the planet where Neko is initially located. Then Aki performs $ k - 1 $ moves, where in each move Neko is moved from the current planet $ x $ to some other planet $ y $ such that: - Planet $ y $ is not visited yet. - $ 1 \leq y \leq x + m $ (where $ m $ is a fixed constant given in the input) This way, Neko will visit exactly $ k $ different planets. Two ways of visiting planets are called different if there is some index $ i $ such that, the $ i $ -th planet visited in the first way is different from the $ i $ -th planet visited in the second way. What is the total number of ways to visit $ k $ planets this way? Since the answer can be quite large, print it modulo $ 10^9 + 7 $ .

The only line contains three integers $ n $ , $ k $ and $ m $ ( $ 1 \le n \le 10^9 $ , $ 1 \le k \le \min(n, 12) $ , $ 1 \le m \le 4 $ ) — the number of planets in the Catniverse, the number of planets Neko needs to visit and the said constant $ m $ .

Print exactly one integer — the number of different ways Neko can visit exactly $ k $ planets. Since the answer can be quite large, print it modulo $ 10^9 + 7 $ .

3 3 1

4

4 2 1

9

5 5 4

120

100 1 2

100

In the first example, there are $ 4 $ ways Neko can visit all the planets: - $ 1 \rightarrow 2 \rightarrow 3 $ - $ 2 \rightarrow 3 \rightarrow 1 $ - $ 3 \rightarrow 1 \rightarrow 2 $ - $ 3 \rightarrow 2 \rightarrow 1 $ In the second example, there are $ 9 $ ways Neko can visit exactly $ 2 $ planets: - $ 1 \rightarrow 2 $ - $ 2 \rightarrow 1 $ - $ 2 \rightarrow 3 $ - $ 3 \rightarrow 1 $ - $ 3 \rightarrow 2 $ - $ 3 \rightarrow 4 $ - $ 4 \rightarrow 1 $ - $ 4 \rightarrow 2 $ - $ 4 \rightarrow 3 $ In the third example, with $ m = 4 $ , Neko can visit all the planets in any order, so there are $ 5! = 120 $ ways Neko can visit all the planets. In the fourth example, Neko only visit exactly $ 1 $ planet (which is also the planet he initially located), and there are $ 100 $ ways to choose the starting planet for Neko.