Vertices of the Implicit Suffix Tree (Hard)

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 "ababa" is depicted in the image below, consisting of 3 nodes:

You are provided with a string s, which is formed by concatenating k copies of the string t. In other words, s = t + t + t + ... + t. Your task is to determine the number of nodes in the implicit suffix tree of the string s.

Input

The first line contains an integer k (1 ≤ k ≤ 10^9). The second line contains the string t (1 ≤ |t| ≤ 10^5). The string t is composed solely of lowercase Latin letters.

Output

Output a single integer representing the number of nodes in the implicit suffix tree of the string s.

Examples