{"problem":{"name":"E. Expectation of Division","description":{"content":"_To be frank with you, this problem is an extension of a classic problem, of which the colossal data range might increase its difficulty._ Let's define a type of operation with respect to a positive ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10225E"},"statements":[{"statement_type":"Markdown","content":"_To be frank with you, this problem is an extension of a classic problem, of which the colossal data range might increase its difficulty._\n\nLet's define a type of operation with respect to a positive integer $n$ as replacing it with one of its positive factor $d$.\n\nGiven the integer $n$ ($n > 1$), you are asked to determine the expected times of doing this operation repeatedly until $n$ is changed into $1$ for the first time, assuming that $d$ is selected with equal probability among all the possible factors at any time.\n\nFor ease of calculation, $n$ and all its distinct prime factors $p_1$, $p_2$, $\\\\dots$, $p_m$ will be given.\n\nTo avoid the precision issue, let's express the expected value as a reduced fraction $frac(a, b)$, and you should output the minimum non-negative integer $c$ such that $b c equiv a pmod 10^9 + 7$.\n\nThe input contains multiple (about $2 times 10^5$) test cases.\n\nFor each test case, the first line contains two integers $n$, $m$ ($2 <= n <= 10^(24)$, $m >= 1$), where $m$ indicates the number of distinct prime factors of $n$.\n\nThe second lines contains $m$ distinct prime numbers $p_1, p_2, \\\\dots, p_m$ ($2 <= p_1, p_2, \\\\dots, p_m <= 10^6$).\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.\n\nIt is guaranteed that the answer exists for each test case.\n\n## Input\n\nThe input contains multiple (about $2 times 10^5$) test cases.For each test case, the first line contains two integers $n$, $m$ ($2 <= n <= 10^(24)$, $m >= 1$), where $m$ indicates the number of distinct prime factors of $n$.The second lines contains $m$ distinct prime numbers $p_1, p_2, \\\\dots, p_m$ ($2 <= p_1, p_2, \\\\dots, p_m <= 10^6$).\n\n## Output\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.It is guaranteed that the answer exists for each test case.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of words.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ be the sequence of words, where each $ w_i $ is a string over lowercase English letters.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 8 \\times 10^6 $  \n2. $ \\sum_{i=1}^{n} |w_i| \\leq 8 \\times 10^6 $  \n3. Each $ w_i $ contains only lowercase English letters.\n\n**Objective**  \nIdentify the set of repeated words as follows:  \nA word $ w_i $ is *repeated* if it has appeared earlier in the sequence (i.e., $ \\exists j < i $ such that $ w_j = w_i $) **and** $ |w_i| \\geq 4 $.  \n\nLet $ R $ be the list of such repeated words, in the order of their *second* (and subsequent) occurrence.  \n\nOutput:  \n- If $ R $ is empty: print `\"SAFO\"`  \n- Otherwise:  \n  1. Print $ |R| $  \n  2. Print all words in $ R $, separated by spaces","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10225E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}