Falling Cherry Blossoms

In the blooming month of April, under a shower of falling sakura petals, Muxii asks his friend ZZH:

“How many sakura petals have fallen in this April?”

ZZH replies:

  The number of petals s and time t obey the relation:
[
s = \prod_{x=1}^{t} \prod_{y\mid x} \frac{y^{d(y)}}{\prod_{z\mid y}(z+1)^2}
]

Here, \(d(y)\) denotes the number of positive divisors of \(y\). Since the number \(s\) can be huge, you are only required to output \(s\) modulo a given prime number \(p\). The input consists of two positive integers \(t\) and \(p\). Compute \(s \bmod p\).

Note: For each integer \(y\) from 1 to \(t\), the inner product is taken over all positive divisors of \(y\), and the outer product is taken over all \(x = 1, 2, \dots, t\). An equivalent reformulation is:

[ s = \prod_{y=1}^{t} \left( \frac{y^{d(y)}}{\prod_{z\mid y}(z+1)^2} \right)^{\lfloor t/y \rfloor}. ]

Your task is to compute \(s \bmod p\).

inputFormat

The input consists of a single line with two integers t and p (with \(p\) being a prime number), separated by a space.

\(1 \le t \le 10^4\) (for example) and \(p\) is a prime number.

outputFormat

Output a single integer representing \(s \bmod p\).

sample

1 1000000007

250000002