题目描述
马上就期末考试了，小智为了放松一下心情，来到了小码的果园摘水果。小智摘了n个完全互不相同的水果，小码看到小智摘了这么多水果，就想考考小智。
小码给小智拿来了k个袋子（每个袋子都非常大，无论多少水果都能装下），他让小智把摘下来的水果装到这k个袋子里，同时要求小智在装水果时要做到每个袋子里都有水果。
如果小智能计算出一共有多少种装法，那么就把这些水果全部免费送给小智。为了方便小码核对小智的答案对不对，要求小智把最后的答案对p求余。
请你帮小智计算出求余后的最后结果。
输入格式
一行三个数，依次为n，k，p。分别代表n个完全互不相同的水果，k个袋子，对p求余。
输出格式
一个数，求余后的结果。
输入样例
4 2 2
输出样例
1
样例说明
一共有4个水果，2个袋子。
共有7种装法
{1}{2,3,4}；{2}{1,3,4}；{3}{1,2,4}；{4}{1,2,3}；{1,2}{3,4}；{1,3}{2,4}；{1,4}{2,3}。
7除以2余1。
数据范围
100%的数据，n<=10000，k<=1000。所有数据n>=k。
且答案在long long范围内。
请问应该怎么做