[2019山东省队集训第一轮]幻化成风
题目描述
给定正整数 n 和一个长度为 m 的正整数数列 a1,a2,…,am。
求有多少种方式选取两两不同的正整数 b1,b2,…,bm,使
n!=i=1∏mbiai.
允许 bi=1,但所有 bi 仍须两两不同。
两种表示方式不同,当且仅当它们的有序数对集合 {(bi,ai):1≤i≤m} 不同。因此,相同指数对应的底数之间仅交换位置,不会产生新的表示方式。
输出不同表示方式数量,对 109+7 取模。
输入格式
第一行两个正整数 n,m。
第二行 m 个正整数 a1,a2,…,am。
输出格式
输出一行一个整数,表示不同表示方式数量对 109+7 取模后的结果。
样例输入 1
10 6
1 2 2 3 3 3
样例输出 1
2
样例解释 1
共有两种表示:
10!=42⋅52⋅42⋅33⋅23⋅13,
10!=21⋅52⋅22⋅43⋅33⋅13.
样例输入 2
20 6
1 2 2 3 3 3
样例输出 2
41680
其他样例
原题样例 3 见选手目录下的 count/count3.in 和 count/count3.ans。
数据范围
所有数据满足 1≤n≤104,1≤m≤30,ai≥1,∑i=1mai≤30。
| 子任务 |
分值 |
n 的上界 |
m 的上界 |
∑ai 的上界 |
| 1 |
20 分 |
10 |
5 |
| 2 |
40 分 |
103 |
10 |
30 |
| 3 |
104 |
30 |