Порой сложно прийти к конечной цене в торге. Вот и Саша с Вовой никак не могут прийти к соглашению – Саша стремится назвать цену как можно больше, а Вова — вычеркнуть из нее как можно больше цифр. Т. е. получается так, что Саша называет какое-то целое число \(n\), Вова вычеркивает из него непустую последовательность подряд идущих цифр, а оставшиеся цифры схлопываются в одно число.
Например, если из числа \(1213121\) вычеркнуть подстроку \(1312\), то получится число \(121\).
Допустима, что итоговая цена содержит ведущие нули. Если Вова вычеркнет все цифры, то считается, что получился \(0\).
Саша хочет как-то ограничить Вову, чтобы тот не вычеркнул все число, но, чтобы у него был правильные аргументы для убеждения, ему нужно знать сумму всех чисел, которые могут получиться после того, как Вова сделает вычеркивание.
Помогите Саше посчитать. А так как число может получиться достаточно большим, то считайте его по модулю \(10^9 + 7\).
Примечание
Рассмотрим первый пример.
Вова может вычеркнуть \(1\), \(0\), \(7\), \(10\), \(07\) или \(107\). Получившиеся числа равны \(07\), \(17\), \(10\), \(7\), \(1\), \(0\). Их сумма равна \(42\).