ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Alice and Bandersnatch

Time limit: 0.5 second
Memory limit: 64 MB
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 ≤ xia − 1) as a key; here, a is the size of the alphabet. Instead of sending Bandersnatch a message s = s1s2sr, she sends a message t = t1t2tr. 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]).

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

inputoutput
3 4
18
10 2
45
Problem Author: Pavel Klimov
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
To submit the solution for this problem go to the Problem set: 1857. Alice and Bandersnatch