{"problem":{"name":"K. Random Numbers","description":{"content":"Tamref love random numbers, but he hates recurrent relations, Tamref thinks that mainstream random generators like the linear congruent generator suck. That's why he decided to invent his own random g","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10146K"},"statements":[{"statement_type":"Markdown","content":"Tamref love random numbers, but he hates recurrent relations, Tamref thinks that mainstream random generators like the linear congruent generator suck. That's why he decided to invent his own random generator. \n\nAs any reasonable competitive programmer, he loves trees. His generator starts with a tree with numbers on each node. To compute a new random number, he picks a rooted subtree and multiply the values of each node on the subtree. He also needs to compute the number of divisors of the generated number (because of cryptographical applications). \n\nIn order to modify the tree (and hence create different numbers on the future), Tamref decided to perform another query: pick a node, and multiply its value by a given number. \n\nGiven a initial tree T, where Tu corresponds to the value on the node u, the operations can be summarized as follows:\n\nTamref is quite busy trying to prove that his method indeed gives integers uniformly distributed, in the meantime, he wants to test his method with a set of queries, and check which numbers are generated. He wants you to write a program that given the tree, and some queries, prints the generated numbers and count its divisors.\n\nTamref has told you that the largest prime factor of both Tu and x is at most the Tamref's favourite prime: 13. He also told you that the root of T is always node 0.\n\nThe figure shows the sample test case. The numbers inside the squares are the values on each node of the tree. The subtree rooted at node 1 is colored. The RAND query for the subtree rooted at node 1 would generate 14400, which has 63 divisors.\n\nThe first line is an integer n (1 ≤ n ≤ 105), the number of nodes in the tree T. Then there are n - 1 lines, each line contains two integers u and v (0 ≤ u, v < n) separated by a single space, it represents that u is a parent of v in T. The next line contains n integers, where the i - th integer corresponds to Ti (1 ≤ Ti ≤ 109). The next line contains a number Q (1 ≤ Q ≤ 105), the number of queries. The final Q lines contain a query per line, in the form \"RAND u\" or \"SEED u x\" (0 ≤ u < n, 1 ≤ x ≤ 109).\n\nFor each RAND query, print one line with the generated number and its number of divisors separated by a space. As this number can be very long, the generated number and its divisors must be printed modulo 109 + 7. \n\n## Input\n\nThe first line is an integer n (1 ≤ n ≤ 105), the number of nodes in the tree T. Then there are n - 1 lines, each line contains two integers u and v (0 ≤ u, v < n) separated by a single space, it represents that u is a parent of v in T. The next line contains n integers, where the i - th integer corresponds to Ti (1 ≤ Ti ≤ 109). The next line contains a number Q (1 ≤ Q ≤ 105), the number of queries. The final Q lines contain a query per line, in the form \"RAND u\" or \"SEED u x\" (0 ≤ u < n, 1 ≤ x ≤ 109).\n\n## Output\n\nFor each RAND query, print one line with the generated number and its number of divisors separated by a space. As this number can be very long, the generated number and its divisors must be printed modulo 109 + 7. \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ nodes, where $ V = \\{0, 1, \\dots, n-1\\} $ and node $ 0 $ is the root.  \nLet $ v: V \\to \\mathbb{Z}^+ $ denote the value assigned to each node, with $ v[u] $ being the value at node $ u $.  \nLet $ \\mathcal{P} = \\{2, 3, 5, 7, 11, 13\\} $ be the set of primes $ \\leq 13 $.  \n\nFor any subtree rooted at node $ u $, define the product $ P(u) = \\prod_{w \\in \\text{subtree}(u)} v[w] $.  \nLet $ \\alpha_p(u) \\in \\mathbb{N} $ denote the exponent of prime $ p \\in \\mathcal{P} $ in the prime factorization of $ P(u) $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq v[u] \\leq 10^9 $ for all $ u \\in V $, and all prime factors of $ v[u] $ are in $ \\mathcal{P} $  \n3. $ 1 \\leq Q \\leq 10^5 $  \n4. For each query:  \n   - `RAND u`: compute $ P(u) \\mod (10^9 + 7) $ and $ d(P(u)) \\mod (10^9 + 7) $, where $ d(P(u)) = \\prod_{p \\in \\mathcal{P}} (\\alpha_p(u) + 1) $  \n   - `SEED u x`: update $ v[u] \\leftarrow v[u] \\cdot x $, where $ 1 \\leq x \\leq 10^9 $ and all prime factors of $ x $ are in $ \\mathcal{P} $  \n\n**Objective**  \nFor each `RAND u` query, output:  \n$$\nP(u) \\mod (10^9 + 7), \\quad \\prod_{p \\in \\mathcal{P}} (\\alpha_p(u) + 1) \\mod (10^9 + 7)\n$$  \nFor each `SEED u x` query, update the value $ v[u] $ and propagate the change in exponents $ \\alpha_p $ for all descendants of $ u $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10146K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}