E. Карусель комбинаций
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$. Значение функции $$$C(i,k)$$$ представляет собой количество различных способов, которыми можно выбрать $$$k$$$ различных чисел из множества {$$$1, 2, \ldots, i$$$} и расположить их по кругу$$$^\dagger$$$.

Найдите значение $$$$$$ \sum\limits_{i=1}^n \sum\limits_{j=1}^i \left( C(i,j) \bmod j \right). $$$$$$ Здесь операция $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.

Поскольку это значение может быть очень большим, найдите его по модулю $$$10^9+7$$$.

$$$^\dagger$$$ Две последовательности считаются одинаковыми расстановками чисел по кругу, если одну из последовательностей можно циклически сдвинуть так, чтобы она совпала с другой. Например, $$$[1, 2, 3]$$$ и $$$[2, 3, 1]$$$ являются одинаковыми расстановками по кругу.

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

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

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).

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

Для каждого набора входных данных выведите на отдельной строке одно число — значение вычисляемого выражения по модулю $$$10^9+7$$$.

Пример
Входные данные
4
1
3
6
314159
Выходные данные
0
4
24
78926217
Примечание

В первом наборе входных данных $$$C(1,1) \bmod 1 = 0$$$.

Во втором наборе входных данных:

  • $$$C(1,1)=1$$$ (способы: $$$[1]$$$);
  • $$$C(2,1)=2$$$ (способы: $$$[1]$$$, $$$[2]$$$);
  • $$$C(2,2)=1$$$ (способы: $$$[1, 2]$$$);
  • $$$C(3,1)=3$$$ (способы: $$$[1]$$$, $$$[2]$$$, $$$[3]$$$);
  • $$$C(3,2)=3$$$ (способы: $$$[1, 2]$$$, $$$[2, 3]$$$, $$$[3, 1]$$$);
  • $$$C(3,3)=2$$$ (способы: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$).
Итого, $$$\left(C(1,1) \bmod 1\right) + \left(C(2,1) \bmod 1\right) + \left(C(2,2) \bmod 2\right) + \left(C(3,1) \bmod 1\right) + \left(C(3,2) \bmod 2\right) + \left(C(3,3) \bmod 3\right) = 4$$$.