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 `x` ≥ `k` × `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 `n`^{th} 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 `n`^{th} 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 10^{th} good rectangle's area is 144*89, and 89 is a good width.

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

Author:

**ZHOU, Yuchen**
Submit
Status