aa
题目背景
2018 年 11 月 17 日,中国香港将会迎来一场XM大战,是世界各地的ENLIGHTENED与RESISTANCE开战的地点,某地 的ENLIGHTENED总部也想派Agent去参加这次的XM大战,与世界其他地方的ENLIGHTENED并肩作战。
题目描述
某地的ENLIGHTENED总部总部有 NN 个Agent,每个Agent的能力值互不相同,现在ENLIGHTENED行动指挥想要派出 A,BA,B 两队Agent去参加XM大战。但是参加大战的两个队伍要满足两个要求:
AA 队中能力最大的Agent的能力值要小于 BB 队能力最弱的Agent的能力值。
A,BA,B 两队都要有人参战。
并不一定所有的Agent都要去参加XM大战的,心急的ENLIGHTENED行动指挥想知道有多少种安排Agent参加大战的方案。由于答案可能很大,所以只需要你求出答案模 (10^9+7)(10
9
+7) 的值就可以了。
输入输出格式
输入格式:
输入仅一行,为一个整数 NN。
输出格式:
输出答案模 (10^9+7)(10
9
+7) 的值。
输入输出样例
输入样例 #1:
3
输出样例 #1:
5
输入样例 #2:
6
输出样例 #2:
129
说明
对于 20\%20% 的数据 N \leq 10N≤10
对于 40\%40% 的数据 N \leq 10^3N≤10
3
对于 60\%60% 的数据 N \leq 10^5N≤10
5
对于 100\%100% 的数据 N \leq 10^9N≤10
9