← 返回题目列表

AtCoder · arc071_d

F. 无限序列

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有多少个无限序列 a_1, a_2, ... 由 {{1, ... ,n}} 满足以下条件吗?

  • 的 n第和后续元素全部相等。也就是说,如果 n \leq i,j, a_i = a_j.
  • 对于每个整数 i, a_i 紧随其后的元素 i第一个元素全部相等。也就是说,如果 i < j < k\leq i+a_i, a_j = a_k.

求计数模数 10^9+7.

约束

  • 1 \leq n \leq 10^6

输入

输入由标准输入按以下格式给出:

n

输出

打印有多少序列满足条件,模 10^9+7.


示例输入 1

2

示例输出 1

4

满足条件的四个序列是:

  • 1, 1, 1, ...
  • 1, 2, 2, ...
  • 2, 1, 1, ...
  • 2, 2, 2, ...

示例输入 2

654321

示例输出 2

968545283