Nice Lineup

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka have \(n\) stallions on their farm, numbered from \(1\) to \(n\).

The farmers want to line up some of their horses in a row.

We call a lineup of \(k\) horses nice if all horses in this lineup have numbers from \(1\) to \(k\) in some order.

For example, the lineups \((2, 1, 3)\), \((1)\), \((4, 3, 2, 1)\) are nice, while \((1, 2, 4, 5)\), \((47)\), \((3, 2)\) are not.

Zenyk and Marichka want to choose some of their horses and line them up. Please calculate how many different nice lineups they can obtain. Two lineups are considered different if they have different lengths, or if horses with different numbers stand at corresponding positions. Since this number can be very large, output the remainder of its division by the integer \(m\).

Input

A single line contains two integers \(n\) and \(m\).

Output

Output an integer — the remainder of the division of the number of different nice lineups by \(m\).

Constraints

\(1 \le n \le 10^9\),

\(1 \le m \le 1000\).

Grading consists of the following subtasks:

• 1 point for each sample from the problem statement,

• 6 points: \(m = 1\),

• 9 points: \(n \le 10\),

• 23 points: \(m = 10\),

• 17 points: \(n \le 1000\),

• 42 points: no additional constraints.

You will receive the points for a subtask only if your program passes all tests in that subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 10	9

Input (stdin) сopy	Output (stdout) сopy
4 7	5

Input (stdin) сopy	Output (stdout) сopy
7 777	474

Notes

In the first example, \(n=3, m=10\). Zenyk and Marichka can choose horses and line them up in \(15\) ways:

• \((1)\) — a nice lineup,

• \((1, 2)\) — a nice lineup,

• \((1, 2, 3)\) — a nice lineup,

• \((1, 3)\),

• \((1, 3, 2)\) — a nice lineup,

• \((2)\),

• \((2, 1)\) — a nice lineup,

• \((2, 1, 3)\) — a nice lineup,

• \((2, 3)\),

• \((2, 3, 1)\) — a nice lineup,

• \((3)\),

• \((3, 1)\),

• \((3, 1, 2)\) — a nice lineup,

• \((3, 2)\),

• \((3, 2, 1)\) — a nice lineup.

In nine ways, the formed lineup is nice. The answer is the remainder of dividing \(9\) by \(10\), which is \(9\).

In the second example, \(n=4, m=7\). Zenyk and Marichka can form \(33\) nice lineups. The answer is the remainder of dividing \(33\) by \(7\), which is \(5\).