Рассмотрим строку \(s\) из \(n\) маленьких английских букв. Пусть \(t_i\) — строка, полученная из \(s\) заменой \(i\)-го символа на символ звёздочки *. Например, если \(s = \mathtt{abc}\), то \(t_1 = \tt{*bc}\), \(t_2 = \tt{a*c}\) и \(t_3 = \tt{ab*}\).
По данной строке \(s\) определите количество различных строк из маленьких латинских букв и звёздочек, которые встречаются как подстроки хотя бы в одной из строк \(\{s, t_1, \ldots, t_n \}\). Пустая строка входит в ответ.
Обратите внимание, что * в данной задаче является обычным символом и не играет специальной роли, как например, в подстановке регулярных выражений.
Выходные данные
Выведите одно число — количество различных подстрок \(s, t_1, \ldots, t_n\).
Примечание
В примере различными подстроками являются: (пустая строка), a, b, c, *, ab, a*, bc, b*, *b, *c, abc, ab*, a*c, *bc.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abc
|
15
|