ВКОШП: ВКОШП 2023

Жители города Партобурга часто нарушают ПДД, попадают в аварии с участием самокатов и угоняют чужие самокаты. Для того, чтобы контролировать происшествия с самокатами, шериф Партобурга ввел систему самокатных номеров.

В первый день каждого месяца шериф выбирает натуральное число \(n\) и печатает все возможные самокатные номера в формате \([a_{1}+a_{2}+ \ldots +a_{k}]\), \(a_1+a_2+\ldots+a_k = n\), натуральные числа \(a_{i}\) упорядочены по неубыванию: \(a_1 \le a_2 \le \ldots \le a_{k}\). Каждый номер уникален — не может быть двух самокатов с одинаковым номером. Номера раздаются владельцам самокатов. Если владельцу не хватило номера в очередной месяц, то использовать самокат в этот месяц он не сможет.

Сам шериф тоже передвигается на самокате. Чтобы его самокат можно было сразу узнать, он имеет номер в особенном формате. Номер самоката шерифа — одно число, которое вычисляется следующим образом. Для всех самокатных номеров текущего месяца \([a_{1}+a_{2}+ \ldots +a_{k}]\) вычисляется значение \(\mathrm{mex}\{a_{1},a_{2}, \ldots, a_{k}\}\) — минимальное натуральное число, отсутствующее в номере. Эти значения суммируются и вычисляется остаток от деления получившейся суммы на \(10^9+7\).

Шериф хочет автоматизировать систему выдачи самокатных номеров и начал со своего. В этом месяце он выбрал число \(n\). Помогите определить, какой номер получит его самокат.