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 x1, …, xn (0 ≤ xi ≤ a − 1) as a key; here, a is the size of the alphabet.
Instead of sending Bandersnatch a message s = s1s2…sr,
she sends a message t = t1t2…tr.
Here, the alphabetic number of letter t1 is the alphabetic number of
letter s1 plus the integer x1, the number of t2 is the number of
s2 plus the integer x2, 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 x1, then x2, and so on
(for example, the number of tn + 1
is the number of sn + 1 plus x1).
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]).
The only line of input contains integers a and n
(1 ≤ a ≤ 26; 1 ≤ n ≤ 10 000).
Output the number of different keys for Alice's cipher.
Problem Author: Pavel Klimov
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011