Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3571
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.

```1 10
2 1
```

```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
Contest: ZOJ Monthly, February 2012
Submit    Status