{"raw_statement":[{"iden":"statement","content":"After your death, you're sent to a mysterious room. There are two cats guarding two doors, one leading to heaven of AC problems and the other leading to hell NO. One cat likes all divisors of an integer a, a being the product of n integers v1, v2, ..., vn. The other cat likes all integers with exactly b divisors. You were asked to count the number of integers that satisfy both cats. If you count correctly, you may go to the heaven of AC problems, full of balloons, otherwise you're sent to hell NO. \n\nAs the answer can be quite large, print the remainder of this number modulo 109 + 7.\n\nThe first line of the input contains two integers b (1 ≤ b ≤ 103) and n (1 ≤ n ≤ 103).\n\nThe following line contains n space separated integers v1, v2, ..., vn (2 ≤ vi ≤ 1012) whose product is a.\n\nOutput a single integer - the number of integers that satisfy both cats modulo 109 + 7.\n\n"},{"iden":"input","content":"The first line of the input contains two integers b (1 ≤ b ≤ 103) and n (1 ≤ n ≤ 103).The following line contains n space separated integers v1, v2, ..., vn (2 ≤ vi ≤ 1012) whose product is a."},{"iden":"output","content":"Output a single integer - the number of integers that satisfy both cats modulo 109 + 7."},{"iden":"examples","content":"Input2 319 5 2Output3Input3 2366 169Output1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected multigraph where:  \n- $ V = \\{1, 2, \\dots, N\\} $ is the set of islands.  \n- $ E = E_{\\text{exist}} \\cup E_{\\text{add}} $, with $ |E_{\\text{exist}}| = M $ (existing bridges) and $ |E_{\\text{add}}| = K $ (candidate bridges to add).  \n\nLet $ d(v) $ denote the degree of vertex $ v \\in V $ in the graph $ G' = (V, E_{\\text{exist}} \\cup E') $, where $ E' \\subseteq E_{\\text{add}} $ is the set of added bridges.\n\n**Constraints**  \n1. $ 1 \\le N \\le 10^5 $, $ 0 \\le M \\le 10^5 $, $ 0 \\le K \\le 10^5 $.  \n2. Each bridge is an unordered pair $ \\{a, b\\} $ with $ a, b \\in V $, $ a \\ne b $.  \n3. Multiple edges between same pair allowed.  \n4. The graph $ (V, E_{\\text{exist}}) $ is connected.  \n\n**Objective**  \nDetermine if there exists a subset $ E' \\subseteq E_{\\text{add}} $ such that in the graph $ G' = (V, E_{\\text{exist}} \\cup E') $:  \n- Every vertex has even degree (i.e., $ d(v) \\equiv 0 \\pmod{2} $ for all $ v \\in V $),  \n- and a closed Eulerian trail exists (which is guaranteed if the graph is connected and all degrees are even).  \n\nIf such $ E' $ exists, output:  \n- \"YES\",  \n- $ R = |E'| $,  \n- the $ R $ edges in $ E' $.  \n\nOtherwise, output \"NO\".","simple_statement":"You are given N islands and M existing bridges. You can add up to K new bridges. Can you add some (or none) of the new bridges so that you can start outside the lake, walk across every bridge exactly once, and return to the start? If yes, output the bridges you need to add.","has_page_source":false}