Лингвист изучает слово и вырезает из него «осколки». Осколок получается, если выбрать несколько символов слова в исходном порядке, возможно пропуская некоторые символы. При этом два осколка считаются одинаковыми, если получающиеся строки совпадают, даже если выбраны разные позиции.

По данному слову определите, сколько различных непустых осколков можно из него вырезать.

Так как ответ может быть очень большим, выведите его по модулю 1000000007.

Входные данные

В единственной строке дано непустое слово из строчных латинских букв длиной не более 2 * 10^5.

Выходные данные

Выведите количество различных непустых осколков по модулю 1000000007.

Ограничения

• 1 <= |s| <= 2 * 10^5
• Строка состоит только из строчных латинских букв.
• Ввод осуществляется через стандартный ввод.
• Вывод осуществляется через стандартный вывод.

Примеры

Пример 1

Входные данные

abc

Выходные данные

7

Пояснение

У 'abc' различные подпоследовательности: a, b, c, ab, ac, bc, abc — всего 7.

Пример 2

Входные данные

a

Выходные данные

1

Пример 3

Входные данные

ab

Выходные данные

3