#P6696. [2019山东省队集训第一轮]幻化成风

    ID: 6546 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-组合数学容斥原理枚举与搜索暴力枚举动态规划状压 DP记忆化搜索完全背包多项式与生成函数普通生成函数重复元素除重阶乘逆元预处理数论埃氏筛CF3000

[2019山东省队集训第一轮]幻化成风

[2019山东省队集训第一轮]幻化成风

题目描述

给定正整数 nn 和一个长度为 mm 的正整数数列 a1,a2,…,ama_1,a_2,\ldots,a_m。

求有多少种方式选取两两不同的正整数 b1,b2,…,bmb_1,b_2,\ldots,b_m,使

n!=∏i=1mbiai.n!=\prod_{i=1}^{m}b_i^{a_i}.

允许 bi=1b_i=1,但所有 bib_i 仍须两两不同。

两种表示方式不同,当且仅当它们的有序数对集合 {(bi,ai):1≤i≤m}\{(b_i,a_i):1\le i\le m\} 不同。因此,相同指数对应的底数之间仅交换位置,不会产生新的表示方式。

输出不同表示方式数量,对 109+710^9+7 取模。

输入格式

第一行两个正整数 n,mn,m。

第二行 mm 个正整数 a1,a2,…,ama_1,a_2,\ldots,a_m。

输出格式

输出一行一个整数,表示不同表示方式数量对 109+710^9+7 取模后的结果。

样例输入 1

10 6
1 2 2 3 3 3

样例输出 1

2

样例解释 1

共有两种表示:

10!=42⋅52⋅42⋅33⋅23⋅13,10!=42\cdot5^2\cdot4^2\cdot3^3\cdot2^3\cdot1^3, 10!=21⋅52⋅22⋅43⋅33⋅13.10!=21\cdot5^2\cdot2^2\cdot4^3\cdot3^3\cdot1^3.

样例输入 2

20 6
1 2 2 3 3 3

样例输出 2

41680

其他样例

原题样例 3 见选手目录下的 count/count3.in 和 count/count3.ans。

数据范围

所有数据满足 1≤n≤1041\le n\le10^4,1≤m≤301\le m\le30,ai≥1a_i\ge1,∑i=1mai≤30\sum_{i=1}^{m}a_i\le30。

子任务 分值 nn 的上界 mm 的上界 ∑ai\sum a_i 的上界
1 20 分 1010 55
2 40 分 10310^3 1010 3030
3 10410^4 3030