Богдан получил на день рождения настольную игру «Сумма на подотрезке». Эта увлекательная настольная игра состоит из $$$n$$$ двусторонних карточек. На каждой сторонах карточки написано некоторое целое число. Карточки выкладываются в ряд на стол и получают номера с 1 до $$$n$$$ слева направо. После этого карточки можно переворачивать, но нельзя менять местами.

Игрок в качестве задания получает номера $$$l$$$ и $$$r$$$, а затем каждую карточку между $$$l$$$-й и $$$r$$$-й включительно размещает одной из сторон наверх. Цель игрока — добиться, чтобы сумма чисел на верхних сторонах карточек от $$$l$$$-й и $$$r$$$-й включительно оказалась максимальной.

Богдану быстро наскучило просто искать максимальную сумму, и он решил усложнить игру. Теперь Богдан выбирает число $$$k$$$, при выполнении задания для карточек от $$$l$$$-й и $$$r$$$-й включительно он переворачивает карточки таким образом, что получившаяся сумма чисел была максимальной, но не делилась на $$$k$$$. Если Богдан выполняет задание с карточками от $$$l$$$-й до $$$r$$$-й, то полученную сумму он обозначает как $$$f(l, r)$$$. Если от $$$l$$$ до $$$r$$$ невозможно выбрать числа на карточках так, чтобы полученная сумма была не кратна $$$k$$$, Богдан считает, что $$$f(l,r)=0$$$.

Наигравшись с карточками, Богдан задумался над такой задачей. Он захотел посчитать сумму всех $$$f(l, r)$$$ для всех возможных пар $$$l$$$ и $$$r$$$, то есть найти $$$\sum\limits_{1 \le l \le r \le n}f(l,r)$$$.

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