题目描述

给定 \(n,m,p,\) 求\((\Sigma_{a_1<=n}^{a_1=1}\Sigma_{a_2<=n}^{a_2=1}...\Sigma_{a_m<=n}^{a_m=1}\Pi_{i<=m}^{i=1}a_i)\%p\)的值。

格式

输入格式

一行 \(3\) 个数， \(n,m,p\)

输出格式

一行一个数，答案

样例1

样例输入1

3 2 10007

样例输出1

36

样例解释

\(1×1+1×2+1×3+2×1+2×2+2×3+3×1+3×2+3×3=36\)

\(36\%10007=36\)

限制

对于\(20\%\)的数据， \(n,m<=8\)

对于\(50\%\)的数据， \(n,m<=10^6\)

对于\(100\%\)的数据， \(n,m<=2^{31}-1,p<=10^9+7\)

提示

\(n<=2^{31}-1\) 使得你的程序效率必须极高

不要尝试着 \(O(n)\) 过