Strange Limit

Consider sequence a_n defined with the following recurrence:

a_1 = p,

a_{n+1} = p^an for n ≥ 1,

where p is some prime number. Let

b_n = a_n 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 b_n has limit as n → +∞. Your task is to find it. Given p and m, find

.

Input

Input file contains p and m (2 ≤ p, m ≤ 12, p is prime).

Output

Output the limit requested.

Examples