{"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 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.\n\n## Constraints\n\n*   All values in the input are integers.\n*   $1 \\le N,K,E_i \\le 10000$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n$E_1$ $E_2$ $\\dots$ $E_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc285_h","tags":[],"sample_group":[["3 2\n3 2","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."],["285 10\n3141 5926 5358 9793 2384 6264 3383 279 5028 8419","672860525\n\nBe sure to find the count modulo $\\color{red}{10^9+7}$."]],"created_at":"2026-03-03 11:01:13"}}