Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2674
Strange Limit

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Consider sequence an defined with the following recurrence:

a1= p,
an+1= pan
for n >= 1,

where p is some prime number. Let

bn = an mod m!,

where m! denotes m factorial, that is m! = 1 · 2 · ... · m.

It may seem strange, but for all p and all m the sequence bn has limit as n . Your task is to find it. Given p and m, find

Input

There are several test cases in the input. Each case contains p and m (2 <= p, m <= 12, p is prime). There is am empty line between each case.

Output

Output the limit requested. There should be am empty line between each case.

Example

InputOutput
2 20
2 34
3 830267

Source: Andrew Stankevich's Contest #8
Submit    Status