J. 简单的指数运算
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个正整数 $$$N$$$ 和一个质数 $$$P$$$ 。

请你计算以下表达式的值：

$$$$$$\prod_{i=1}^N \prod_{j=1}^N (i \cdot j)^{d(i \cdot j)} \pmod {P}$$$$$$

其中，$$$d(x)$$$ 为 $$$x$$$ 的正因数的数目。也就是说，$$$d(x) = \sigma_0(x) = \sum_{d | x}1$$$ 。

Input

仅一行，包含两个正整数 $$$N$$$ 和 $$$P$$$ ($$$1 \leq N \leq 10^6, 10^7+19 \leq P \leq 10^9+7$$$) ，用空格分隔，含义如题面所述。

输入数据保证 $$$P$$$ 是质数。

Output

仅一行，包含一个整数，为上述表达式的值。

Examples
Input
2 998244353
Output
1024
Input
114514 1000000007
Output
925016843