#P17975. [AMPPZ 2025]Count Triangular Sequences

[AMPPZ 2025]Count Triangular Sequences

Count Triangular Sequences

时间限制:1 秒。空间限制:1024 MiB。

题目描述

给定整数 nn。一个整数序列称为“三角形序列”,当且仅当它满足以下条件:

  • 序列长度不超过 nn;
  • 每个元素均在 [1,n][1,n] 内;
  • 可以选出三个不同位置,使这三个位置上的数能作为一个非退化三角形的三条边长。

非退化三角形的面积必须为正,即最大边长严格小于另两条边长之和。

求三角形序列的数量,对 109+710^9+7 取模。序列有顺序,改变元素顺序可能得到不同序列;元素允许重复。

输入格式

一行一个整数 nn。

输出格式

一行一个整数,表示答案对 10000000071000000007 取模的结果。

数据范围

3≤n≤2000003\le n\le200000。

样例 1

输入

3

输出

15

样例 2

输入

4

输出

254

说明

例如,当 n=100n=100 时,(1,1,1)(1,1,1) 是合法序列,(16,1,11,25,100)(16,1,11,25,100) 也合法,因为可以选择边长 16,11,2516,11,25。

(16,1,11,84,100)(16,1,11,84,100) 不合法,因为无论选择哪三个位置,都不能组成非退化三角形。(5,5)(5,5) 也不合法,因为长度不足三。