Вам дано целое число \(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]\) являются одинаковыми расстановками по кругу.
Примечание
В первом наборе входных данных \(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\).