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$.