超级麻将（mahjong）

题目描述

$\text{Alpha}$ 已经不屑于打麻将了，于是他开始研究胡牌概率。

对于普通麻将， $\text{Alpha}$ 已经对这个概率了如指掌，于是他发明了超级麻将。这样的麻将有 $s$ 种花色，每种花色 $n$ 种牌，每种牌有 $4$ 张，胡牌需要 $3t+2$ 张牌，即需要 $t$ 个顺子或刻字以及一个对子。

刻字指的是 $3$ 张一样的牌;

顺子指的是 $3$ 个同花色且连续的牌;

对子指两张一样的牌。

在传统的麻将中，$n = 9,s = 3,t = 4$。

$\text{Alpha}$ 想计算在超级麻将中，有多少种可能的胡牌局面。两个局面不同，当且仅当存在一种牌在两个局面中的张数不同。

输入格式

一行 $3$ 个数分别表示 $n,s,t$。

输出格式

一个整数表示答案，答案对 $10^9+7$ 取模。

样例1

输入样例

4 1 1 

输出样例

20

样例2

见下发样例

数据范围

• 子任务1(10分)： $n,s,t ≤ 10$。

• 子任务2(10分)： $n,s ≤1000,t ≤ 10$。

• 子任务3(10分)：$n ≤1000,t ≤ 10$。

• 子任务4(10分)： $n ≤1000$。

• 子任务5(10分)：$s,t ≤5$。

• 子任务6(10分)：$t ≤ 10$。

• 子任务7(10分)： $t≤20$。

• 子任务8(10分)：$t≤30$。

• 子任务9(10分)：$t≤50$。

• 子任务10(10分)：$t≤60$。

注意：$n,s$ 如无特别说明，默认范围 $3 \leq n,s< 10^{18}$