Vertices of the implicit suffix tree#5915
An implicit suffix tree is a tree that contains all suffixes of a string in the form of an implicit trie, and among such structures, contains the minimum possible number of nodes. For example, the implicit suffix tree for the string is shown in the figure below (it contains nodes):
You are given a string , which is constructed by concatenating copies of a string . That is,
Count 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), consisting only of lowercase Latin letters.
Print a single integer — the number of nodes in the implicit suffix tree of the string .
Example 1