CF113B Petr#

Long ago, when Petya was a schoolboy, he was very much interested in the Petr# language grammar. During one lesson Petya got interested in the following question: how many different continuous substrings starting with the $ s_{begin} $ and ending with the $ s_{end} $ (it is possible $ s_{begin}=s_{end} $ ), the given string $ t $ has. Substrings are different if and only if their contents aren't equal, their positions of occurence don't matter. Petya wasn't quite good at math, that's why he couldn't count this number. Help him!

N/A

N/A

In the third sample there are four appropriate different substrings. They are: ab, abab, ababab, abababab. In the fourth sample identificators intersect.