/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
整数 N,K と長さ K の数列 E が与えられます。
長さ N の正整数列であって、以下の条件を全て満たすものの総数を \color{red}{10^9+7} で割った余りを求めてください。
- どの要素も平方数でない
- 全要素の積が \displaystyle \prod_{i=1}^{K} p_i^{E_i} である
但し、
- p_i は小さい方から i 番目の素数を指すものとします。
- ある 2 つの長さが等しい正整数列 A,B について、 A の i 項目と B の i 項目が異なるような整数 i が存在する時に限り、 A と B は異なる列であるとします。
制約
- 入力は全て整数
- 1 \le N,K,E_i \le 10000
入力
入力は以下の形式で標準入力から与えられる。
N K E_1 E_2 \dots E_K
出力
答えを整数として出力せよ。
入力例 1
3 2 3 2
出力例 1
15
全要素の積が 72=2^3 \times 3^2 となる長さ 3 の数列は以下です。
- (1,1,72) とその並べ替え ( 3 通り ) ... 1 が平方数なので、条件を満たしません。
- (1,2,36) とその並べ替え ( 6 通り ) ... 1,36 が平方数なので、条件を満たしません。
- (1,3,24) とその並べ替え ( 6 通り ) ... 1 が平方数なので、条件を満たしません。
- (1,4,18) とその並べ替え ( 6 通り ) ... 1,4 が平方数なので、条件を満たしません。
- (1,6,12) とその並べ替え ( 6 通り ) ... 1 が平方数なので、条件を満たしません。
- (1,8,9) とその並べ替え ( 6 通り ) ... 1,9 が平方数なので、条件を満たしません。
- (2,2,18) とその並べ替え ( 3 通り ) ... 条件を満たします。
- (2,3,12) とその並べ替え ( 6 通り ) ... 条件を満たします。
- (2,4,9) とその並べ替え ( 6 通り ) ... 4,9 が平方数なので、条件を満たしません。
- (2,6,6) とその並べ替え ( 3 通り ) ... 条件を満たします。
- (3,3,8) とその並べ替え ( 3 通り ) ... 条件を満たします。
- (3,4,6) とその並べ替え ( 6 通り ) ... 4 が平方数なので、条件を満たしません。
よって、条件を満たす数列は 15 個です。
入力例 2
285 10 3141 5926 5358 9793 2384 6264 3383 279 5028 8419
出力例 2
672860525
\color{red}{10^9+7} で割った余りを求めることに注意してください。
Score : 600 points
Problem Statement
You are given integers N and K, and a sequence E of length K.
Find the number, modulo \color{red}{10^9+7}, of sequences of length N consisting of positive integers that satisfy the following conditions:
- no element is a square number;
- the product of all elements is \displaystyle \prod_{i=1}^{K} p_i^{E_i}.
Here,
- p_i denotes the i-th smallest prime.
- Two sequences A and B of the same length consisting of positive integers are considered different if and only if there exists an integer i such that the i-th terms of A and B are different.
Constraints
- All values in the input are integers.
- 1 \le N,K,E_i \le 10000
Input
The input is given from Standard Input in the following format:
N K E_1 E_2 \dots E_K
Output
Print the answer as an integer.
Sample Input 1
3 2 3 2
Sample Output 1
15
The sequences of length 3 whose total product is 72=2^3 \times 3^2 are listed below.
- (1,1,72) and its permutations (3 instances) are inappropriate because 1 is a square number.
- (1,2,36) and its permutations (6 instances) are inappropriate because 1 and 36 are square numbers.
- (1,3,24) and its permutations (6 instances) are inappropriate because 1 is a square number.
- (1,4,18) and its permutations (6 instances) are inappropriate because 1 and 4 are square numbers.
- (1,6,12) and its permutations (6 instances) are inappropriate because 1 is a square number.
- (1,8,9) and its permutations (6 instances) are inappropriate because 1 and 9 are square numbers.
- (2,2,18) and its permutations (3 instances) are appropriate.
- (2,3,12) and its permutations (6 instances) are appropriate.
- (2,4,9) and its permutations (6 instances) are inappropriate because 4 and 9 are square numbers.
- (2,6,6) and its permutations (3 instances) are appropriate.
- (3,3,8) and its permutations (3 instances) are appropriate.
- (3,4,6) and its permutations (6 instances) are inappropriate because 4 is a square number.
Therefore, 15 sequences satisfy the conditions.
Sample Input 2
285 10 3141 5926 5358 9793 2384 6264 3383 279 5028 8419
Sample Output 2
672860525
Be sure to find the count modulo \color{red}{10^9+7}.