{"raw_statement":[{"iden":"problem statement","content":"You are given integers $N$ and $K$, and a sequence $E$ of length $K$.  \nFind the number, modulo $\\color{red}{10^9+7}$, of sequences of length $N$ consisting of positive integers that satisfy the following conditions:\n\n*   no element is a square number;\n*   the product of all elements is $\\displaystyle \\prod_{i=1}^{K} p_i^{E_i}$.\n\nHere,\n\n*   $p_i$ denotes the $i$\\-th smallest prime.\n*   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."},{"iden":"constraints","content":"*   All values in the input are integers.\n*   $1 \\le N,K,E_i \\le 10000$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$E_1$ $E_2$ $\\dots$ $E_K$"},{"iden":"sample input 1","content":"3 2\n3 2"},{"iden":"sample output 1","content":"15\n\nThe sequences of length $3$ whose total product is $72=2^3 \\times 3^2$ are listed below.\n\n*   $(1,1,72)$ and its permutations ($3$ instances) are inappropriate because $1$ is a square number.\n*   $(1,2,36)$ and its permutations ($6$ instances) are inappropriate because $1$ and $36$ are square numbers.\n*   $(1,3,24)$ and its permutations ($6$ instances) are inappropriate because $1$ is a square number.\n*   $(1,4,18)$ and its permutations ($6$ instances) are inappropriate because $1$ and $4$ are square numbers.\n*   $(1,6,12)$ and its permutations ($6$ instances) are inappropriate because $1$ is a square number.\n*   $(1,8,9)$ and its permutations ($6$ instances) are inappropriate because $1$ and $9$ are square numbers.\n*   $(2,2,18)$ and its permutations ($3$ instances) are appropriate.\n*   $(2,3,12)$ and its permutations ($6$ instances) are appropriate.\n*   $(2,4,9)$ and its permutations ($6$ instances) are inappropriate because $4$ and $9$ are square numbers.\n*   $(2,6,6)$ and its permutations ($3$ instances) are appropriate.\n*   $(3,3,8)$ and its permutations ($3$ instances) are appropriate.\n*   $(3,4,6)$ and its permutations ($6$ instances) are inappropriate because $4$ is a square number.\n\nTherefore, $15$ sequences satisfy the conditions."},{"iden":"sample input 2","content":"285 10\n3141 5926 5358 9793 2384 6264 3383 279 5028 8419"},{"iden":"sample output 2","content":"672860525\n\nBe sure to find the count modulo $\\color{red}{10^9+7}$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}