题目描述

王老师 最近做了一道经典问题《翻纸牌》

现在 王老师 有 $n$ 张牌，编号分别为 $1,2,3…n$，每张牌一开始都是背面朝上的现在他要进行 $n$ 轮操作，第 $i$ 轮操作时候，他会将所有编号是 $i$ 的倍数的牌正反翻面现在 王老师 想知道，当他进行完 $n$ 轮操作以后，所有正面朝上的牌的编号总和是多少因为数字可能很大，所以请你将答案对 $10^9 +7$ 取模

输入格式

一个整数 $n$，表示有 $n$ 张牌

输出格式

一个整数，表示正面朝上的牌编号总和，并对 $10^9 +7$ 取模

样例输入 1

5

样例输出 1

5

样例输入 2

20

样例输出 2

30

样例输入 3

662899

样例输出 3

180115815

提示/说明

样例 1 解释

第1轮操作，把第1~5张牌全翻成正面，1 1 1 1 1

第2轮操作，把第2、4张牌翻成反面，1 0 1 0 1

第3轮操作，把第3张牌翻成反面，1 0 0 0 1

第4轮操作，把第4张牌翻成正面，1 0 0 1 1

第5轮操作，把第5张牌翻成反面，1 0 0 1 0

最后只有第1张牌和第4张牌是正面，所以编号总和为5

数据范围

对于 30% 的数据：$1≤n≤10^6$

对于 60% 的数据：$1≤n≤10^{14}$

对于 100% 的数据：$1≤n≤10^{18}$