The Queen turned crimson with fury, and <…> screamed “Off with her head! Off—”
After talking to the Queen of Hearts, Alice understood one important thing:
one inappropriate word can make you beheaded.
So, Alice started to cipher her dialogues with her new friend Bandersnatch.
Recently she happened to invent a cipher which is easy in use, yet secure.
Alice uses a sequence of integers x_{1}, …, x_{n} (0 ≤ x_{i} ≤ a − 1) as a key; here, a is the size of the alphabet.
Instead of sending Bandersnatch a message s = s_{1}s_{2}…s_{r},
she sends a message t = t_{1}t_{2}…t_{r}.
Here, the alphabetic number of letter t_{1} is the alphabetic number of
letter s_{1} plus the integer x_{1}, the number of t_{2} is the number of
s_{2} plus the integer x_{2}, and so on; naturally, the next after the
last letter of the alphabet is the first one.
After pronouncing the first n letters of her message, Alice uses
her sequence from the beginning by using x_{1}, then x_{2}, and so on
(for example, the number of t_{n + 1}
is the number of s_{n + 1} plus x_{1}).
Alice wants to know the number of different keys for her cipher.
The keys that can be obtained from each other by a cyclic shift
(e. g., [0, 1, 2, 0] and [2, 0, 0, 1]) are considered the same.
Moreover, Alice is afraid of eavesdropping, so she doesn't want to use
sequences with period less than n
(these are the sequences of length n which can be represented
as shorter sequences repeated some integer number of times, like [0, 1, 0, 1]).
Input
The only line of input contains integers a and n
(1 ≤ a ≤ 26; 1 ≤ n ≤ 10 000).
Output
Output the number of different keys for Alice's cipher.
Samples
input  output 

3 4
 18

10 2
 45

Problem Author: Pavel Klimov
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011