题目描述

求

$$\sum_{i=1}^n\sum_{j=1}^n\gcd(fib_i,fib_j)\bmod (10^9+7)$$

其中$fib_i$为斐波那契数列的第$i$项。

$$fib_1=1,fib_2=1\\ \forall i\geq 3,fib_i=fib_{i-1}+fib_{i-2}$$

输入格式

一个正整数$n$。

输出格式

所求的答案。

样例

样例输入 #1

3

样例输出 #1

10

样例输入 #2

10

样例输出 #2

251

样例输入 #3

114514

样例输出 #3

364695582

样例输入 #4

1919810

样例输出 #4

320000104

样例输入 #5

19260817

样例输出 #5

484091873

数据范围

子任务编号	$n\le$	分值
1	$10$	10
2	$10^3$	20
3	$10^5$	30
4	$10^{10}$	40