众所周知有如下恒等式对任意正整数 成立：
如何将此性质推广到一般情况呢？
设
给定正整数 ，保证 为质数，求 中 的 次项系数。 答案可能很大，只需要输出其对 取模的结果即可。
一行三个正整数 。
输出一行一个整数，表示答案对 取模的结果。
2 4 3
258593760
5 6 6
177906112
3 18 8
566697133
2 24 17
401935277
2 96 18
36903708
本题采用捆绑测试。
Subtask 1（10 pts）：; Subtask 2（20 pts）：； Subtask 3（30 pts）：； Subtask 4（40 pts）：无特殊限制。
对于全部的数据，，，。
