说明

本题不再额外提供样例文件。

题目描述

有 N 种商品，其中第 i 种商品恰好有 i 件，单价恰好为 i 元。

你手中恰好有 N 元钱。

问：你有多少种购买方案可以把手中的钱恰好花光？答案可能很大，你只需要输出 答案 mod P，其中 P 是输入的一个数。

两种购买方案不同，当且仅当存在一种商品的购买数量不同。

输入格式

一行，包含两个整数 N, P。

输出格式

一行，包含一个整数，表示答案。

样例1输入

3 123

样例1输出

2

样例2输入

12345 123456789

样例2输出

52357216

数据范围

10% 的数据： $N ≤ 10$

30% 的数据： $N ≤ 10^3$

50% 的数据： $N ≤ 10^4$

100% 的数据： $N ≤ 10^5$, $P ≤ 10^9$