C. Странная функция
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Положим $$$f(i)$$$ равным наименьшему положительному целому числу $$$x$$$ такому, что $$$x$$$ не является делителем $$$i$$$.

Посчитайте $$$\sum_{i=1}^n f(i)$$$ по модулю $$$10^9+7$$$. Иными словами, посчитайте $$$f(1)+f(2)+\dots+f(n)$$$ по модулю $$$10^9+7$$$.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$) – количество наборов входных данных. Далее следует описание $$$t$$$ наборов входных данных.

Каждая строка, описывающая набор входных данных, содержит единственное целое число $$$n$$$ ($$$1\leq n\leq 10^{16}$$$).

Выходные данные

Для каждого набора входных данных выведите единственное целое число $$$ans$$$, где $$$ans=\sum_{i=1}^n f(i)$$$ по модулю $$$10^9+7$$$.

Пример
Входные данные
6
1
2
3
4
10
10000000000000000
Выходные данные
2
5
7
10
26
366580019
Примечание

В четвертом наборе $$$n=4$$$, поэтому $$$ans=f(1)+f(2)+f(3)+f(4)$$$.

  • $$$1$$$ делит $$$1$$$, но $$$2$$$ – не делит, поэтому $$$2$$$ является наименьшим положительным целым числом, которое не делит $$$1$$$. Таким образом, $$$f(1)=2$$$.
  • $$$1$$$ и $$$2$$$ делят $$$2$$$, но $$$3$$$ – не делит, поэтому $$$3$$$ является наименьшим положительным целым числом, которое не делит $$$2$$$. Таким образом, $$$f(2)=3$$$.
  • $$$1$$$ делит $$$3$$$, но $$$2$$$ – не делит, поэтому $$$2$$$ является наименьшим положительным целым числом, которое не делит $$$3$$$. Таким образом, $$$f(3)=2$$$.
  • $$$1$$$ и $$$2$$$ делят $$$4$$$, но $$$3$$$ – не делит, поэтому $$$3$$$ является наименьшим положительным целым числом, которое не делит $$$4$$$. Таким образом, $$$f(4)=3$$$.

Получаем: $$$ans=f(1)+f(2)+f(3)+f(4)=2+3+2+3=10$$$.