在农历新年期间，Bugcat 一直在玩一款以麻将为主题的“roguelike”游戏（类似于《小丑牌》Balatro）。在这个游戏中，Bugcat 从牌堆中摸牌并弃牌，并且它对“牌墙”（即牌堆）中的牌的顺序了如指掌。

Bugcat 开始思考：如果有一副包含 $n$ 种不同牌型的麻将，在假设最优策略的情况下，要凑齐一副“四暗刻”（Sūankō）手牌，期望需要摸多少张牌（包括初始的 13 张牌）？输出结果模 $10^9 + 7$ 的值。

定义：

• 麻将牌组：共有 $n$ 种牌。每种牌恰好有 4 张外观相同但彼此不同的牌。因此，牌堆中总共有 $4n$ 张牌。
• 四暗刻：一个“刻子”（或三张相同牌）定义为 3 张相同种类的牌。要完成这副手牌，你需要四个刻子和一个对子（2 张相同种类的牌）。

简化题意

有 $4n$ 张牌，分为 $n$ 种颜色（种类），每种颜色有 4 张牌。即使是相同颜色的牌也被视为是不同的。

考虑牌堆的所有 $(4n)!$ 种可能的排列。对于给定的排列，定义“代价”为最小的索引 $i$，使得在序列的前 $i$ 张牌中，满足以下两个条件：

• 至少有 4 种颜色出现了 3 次或更多次。
• 至少有 5 种颜色出现了 2 次或更多次。

求在所有可能排列中代价 $i$ 的期望值。输出结果模 $10^9 + 7$ 的值。

输入格式

一个整数 $n$ ($1 \le n \le 2 \times 10^6$)，表示牌的种类数。

输出格式

一个整数，表示期望代价模 $10^9 + 7$ 的值。

样例

输入样例 1

5

输出样例 1

80495372

输入样例 2

4

输出样例 2

0