Вам дано целое число $$$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$$$.
4136314159
0 4 24 78926217
В первом наборе входных данных $$$C(1,1) \bmod 1 = 0$$$.
Во втором наборе входных данных:
Название |
---|