Description

这是一个小清新的数论题......吗？

给定 $n,k,p$，保证 $p$ 是质数，求

$$\operatorname{lcm}(C_k^k,C_{k+1}^{k},\dots,C_{n}^{k})\pmod{p}^{1}$$

*$^1$$C_n^k$（组合数）表示从 $n$ 个不同元素中不考虑顺序地选出 $k$ 个元素的所有可能方式的数量，计算公式为 $\frac{n!}{k!(n-k)!}$。等价于$\binom{n}{k}$

Format

Input

仅一行，三个正整数 $n,k,p$。保证 $1\leq k<n\leq 10^6,10^8\leq p\leq 10^9$，且 $p$ 是质数。

Output

输出一个数表示答案。

Samples

5 3 998244353

20

1000000 500000 998244353

976108482