Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
113 - ZOJ Monthly, February 2012 - A
Good Rectangle

Time Limit: 2 Seconds      Memory Limit: 32768 KB

We need k square pieces cut from a rectangular piece of paper with length a and width b. Here we assume a is greater than b. Obviously, the biggest side length of a square we can get is b, so the length a of the rectangular piece must be greater than k × b. And after k squares got, the rest part of original rectangle should be a rectangular piece with length b and width c = a - b × k. Here we assume b is not less than c, or we will waste too much. To reuse the rest part, we want the rest rectangle is similar to the original rectangle, but it is impossible (can you prove?).

To measure how similar is the rest rectangle to the original rectangle, we define best(b) = min {abs( b ÷ ( x - k × b ) - x ÷ b ) | for xk × b}. We call b is a good width if best(b) is less than best(d) for any positive d less than b. And if a rectangle with a good width b and a length a which makes abs(b ÷ (a - k × b) - a ÷ b) minimal, it is a good rectangle. We can get the result easily for each good width, a good rectangle can be got. And we sort the good rectangles by its width from small to large. Now given k, can you calculate area of the nth good rectangle? (all variables above is integer)

Input

There are no more than test cases. Each test case has only one line, containing two integers k and n (0 < k < 1000001, 0 < n < 1000001).

Output

Output one line for each case, each case need only a number contained one integer S, which indicates the area of the nth good rectangle. S may be very large, so print S MOD 9875321.

Sample Input

1 10
2 1

Sample Output

12816
3

Hint


In case 1, k=1, the 10th good rectangle's area is 144*89, and 89 is a good width.

In case 2, k=2, the 1st good rectangle's area is 3*1, and 1 is a good width.


Author: ZHOU, Yuchen
Submit    Status