题目描述

求长度为 $n$ 的 $1 \sim n$ 的所有排列总数，其中满足 $p_i \bmod p_{i+1} \leq 2$ 的（此处 $p_{n+1} = p_1$），对 $10^9 + 7$ 取模后的值。

输入格式

一个整数 $n\ (1 \leq n \leq 10^6)$。

输出格式

输出答案模 $10^9+7$ 后的值。

1

1

2

2

3

6

4

16

5

40

1000000

581177467