Ex - Avoid Square Number

AtCoder

IDabc285_h

Time3000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

3 2
3 2

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.

Input #2

285 10
3141 5926 5358 9793 2384 6264 3383 279 5028 8419

Output #2

672860525

Be sure to find the count modulo $\color{red}{10^9+7}$.

API Response (JSON)

{
  "problem": {
    "name": "Ex - Avoid Square Number",
    "description": {
      "content": "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 follo",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc285_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 follo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments