题目描述

由 $\{1, \ldots, n\}$ 组成的无限长序列 $a_1, a_2, \ldots$ 中，满足以下条件的序列有多少种？

• 从第 $n$ 项起，所有项都相同。也就是说，当 $n \leq i, j$ 时，有 $a_i = a_j$。
• 对于任意正整数 $i$，在第 $i$ 项之后连续的 $a_i$ 个项都必须相同。也就是说，若 $i < j < k \leq i + a_i$，则有 $a_j = a_k$。

请输出满足条件的序列数对 $10^9+7$ 取模的结果。

输入格式

输入通过标准输入以如下格式给出。

$n$

输出格式

请输出满足条件的序列数对 $10^9+7$ 取模的结果。

样例 1

输入

2

输出

4

样例 2

输入

654321

输出

968545283

说明/提示

制约条件

• $1 \leq n \leq 10^6$
• $n$ 为整数

样例解释 1

共有以下 $4$ 种情况：

• $1, 1, 1, \ldots$
• $1, 2, 2, \ldots$
• $2, 1, 1, \ldots$
• $2, 2, 2, \ldots$

由 ChatGPT 5 翻译