麻将游戏是用属于 $s$ 花色 的牌进行的。每个牌还有一个范围为 $1\dots n$ 的数字，并且对于每个花色/数字组合，恰好有四个具有该花色和数字的无法区分的牌。 （真正的麻将游戏还包含其他奖励牌，但这些不会出现在这个问题中。）

获胜手牌是 $3t+2$ 牌的集合（其中 $t$ 是固定整数），可以排列为 $t$ 三元组 和一个对子，其中：

• Triple 可以是 Chow 或 Pung
• Chow 是三张相同花色和连续数字的牌
• Pung 是三张相同的牌（相同的花色和相同的数字）
• 对是两张相同的牌（相同的花色和相同的数字）

例如，这是一手获胜牌，$n=9$、$s=3$、$t=4$，在这种情况下包括两个 Chows、两个 Pungs 和一对：

请注意，有时相同的图块集合可以以多种方式表示为 $t$ 三元组和一对。这仅算作一手获胜牌。例如，这被认为是与上面相同的获胜手牌，因为它由相同的牌组成：

令 $w(n,s,t)$ 为由 $t$ 三元组和一对组成的不同获胜手牌的数量，其中有 $s$ 花色可用，牌号最多为 $n$。

例如，单套花色和牌数最多为 $4$，我们有 $w(4,1,1)=20$：有 $12$ 获胜手牌由 Pung 和 Pung 组成，另外 $8$ 包含 Chow 和 Pair。您还可以得到 $w(9,1,4)=13259$、$w(9,3,4)=5237550$ 和 $w(1000,1000,5)\equiv 107662178(\mathrm{mod}1000000007)$。

查找 $w({10}^8,{10}^8,30)$。以 $1000000007$ 为模给出你的答案。