Vertices of the implicit suffix tree

An implicit suffix tree is defined as a tree that includes all suffixes of a string in the form of an implicit trie, with the fewest possible nodes. For instance, the implicit suffix tree for the string "ababa" is depicted in the figure below (it contains 3 nodes):

You are provided with a string s, which is formed by concatenating k copies of the string t. In other words, . 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). The string t is composed solely of lowercase Latin letters.

Output

Print a single integer — the number of nodes in the implicit suffix tree of the string s.

Examples