Марсианского мальчика зовут s — это имя ему совсем недавно дали родители на совершеннолетие. Теперь ему всюду нравится искать свое имя. Если он видит, что из какой-то строки может быть получено его имя путем удаления нуля или более букв (при этом, оставшиеся буквы остаются в том же порядке), то он очень радуется. Например, если s=«aba», то при виде строк «baobab», «aabbaa», «helloabahello» он очень радуется, а при виде строк «aab», «baaa» и «helloabhello» — нет.

Однако вдвое больше чем радоваться один раз, он любит радоваться два раза! Поэтому, получив в подарок строку t, он хочет разрезать ее на две части (левую и правую) так, чтобы каждая из них его очень радовала.

Помогите s определить количество различных способов разрезать заданную строку t на две части искомым образом.