Vertices of the Implicit Suffix Tree (Hard)#5943
An implicit suffix tree is a data structure that represents all suffixes of a string as an implicit trie with the fewest possible nodes.
For instance, the implicit suffix tree for the string "" is depicted in the image below, consisting of nodes:
You are provided with a string , which is formed by concatenating copies of the string . In other words, s = t + t + t + \ldots + t. Your task is to determine the number of nodes in the implicit suffix tree of the string .
The first line contains an integer (1 \le k \le 10^9). The second line contains the string (1 \le |t| \le 10^5). The string is composed solely of lowercase Latin letters.
Output a single integer representing the number of nodes in the implicit suffix tree of the string .
Example 1