#P2655. calc

    ID: 1710 传统题 1000ms 512MiB 尝试: 796 已通过: 369 难度: 7 上传者: 标签>CF2300提高+/省选-0/1 背包倒序更新避免重复使用连续点值插值阶乘逆元预处理前后缀分解排列数计算快速幂

calc

题目描述

一个序列 a1,…,ana_1,\dots,a_n 是合法的,当且仅当: 长度为给定的 nn。a1,…,ana_1,\dots,a_n 都是 [1,A][1,A] 中的整数。a1,…,ana_1,\dots,a_n 互不相等。一个序列的值定义为它里面所有数的乘积,即 ∏i=1nai\prod\limits_{i=1}^{n}a_i。

求所有不同合法序列的值的和。两个序列不同当且仅当他们任意一位不一样。输出答案对一个数 modmod 取余的结果。

输入格式

一行 33 个数,A,n,modA,n,mod。意义为上面所说的。

输出格式

一行结果。

样例

9 7 10007
3611

数据规模和约定

对于 5%5\% 的数据 A,n≤10A,n\le10。

对于 20%20\% 的数据 A≤103,n≤20A\le 10^3,n\le 20。

对于 50%50\% 的数据 A≤109,n≤20A\le 10^9,n\le 20。

对于 100%100\% 的数据 A≤109,n≤500A\le 10^9,n\le 500,mod≤109mod \le 10^9 且为素数,mod>A>n+1mod > A>n+1。