, if has units and the -th unit has size and tier , then she can trade them all in to get a single unit of size and tier .

is playing the latest autobattler game, Team Underground Chess. Each unit in this game is uniquely determined by two traits: size and tier. Players have the option of trading in units in to obtain better units. Specifically, for any positiveFor example, if she has units that are exactly:

- Size and tier
- Size and tier
- Size and tier
- Size and tier

Then she can trade them all in to get a single unit with size and tier .

It costs gold to purchase a unit of size and tier . Higher tier units cannot be purchased directly. starts with no units. How much gold will it cost for her to get a unit of size and tier ? Since this number can be huge, output it modulo the prime number .

#### Constraints

For 20% of the points,

#### Input Specification

A single line with two integers: and .

#### Output Specification

A single integer, the answer, modulo .

#### Sample Input 1

`3 3`

#### Sample Output 1

`10`

#### Explanation for Sample 1

To get a unit of size and tier , needs to trade in:

- A unit with size and tier , which can only be obtained by trading in:
- A unit with size and tier , which can be bought for gold

- A unit with size and tier , which can only be obtained by trading in:
- A unit with size and tier , which can be bought for gold
- A unit with size and tier , which can be bought for gold

- A unit with size and tier , which can only be obtained by trading in:
- A unit with size and tier , which can be bought for gold
- A unit with size and tier , which can be bought for gold
- A unit with size and tier , which can be bought for gold

The total amount of gold she has to spend is .

#### Sample Input 2

`123456 654321`

#### Sample Output 2

`372912936`

#### Explanation for Sample 2

Be careful to output the answer modulo and beware of overflow.

## Comments