{"problem":{"name":"E. Prince's Problem","description":{"content":"Let the main characters of this problem be personages from some recent movie. New Avengers seem to make a lot of buzz. I didn't watch any part of the franchise and don't know its heroes well, but it w","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF986E"},"statements":[{"statement_type":"Markdown","content":"Let the main characters of this problem be personages from some recent movie. New Avengers seem to make a lot of buzz. I didn't watch any part of the franchise and don't know its heroes well, but it won't stop me from using them in this problem statement. So, Thanos and Dr. Strange are doing their superhero and supervillain stuff, but then suddenly they stumble across a regular competitive programming problem.\n\nYou are given a tree with $n$ vertices.\n\nIn each vertex $v$ there is positive integer $a_{v}$.\n\nYou have to answer $q$ queries.\n\nEach query has a from $u$ $v$ $x$.\n\nYou have to calculate $\\prod_{w \\in P} gcd(x, a_{w}) \\mod (10^{9} + 7)$, where $P$ is a set of vertices on path from $u$ to $v$. In other words, you are to calculate the product of $gcd(x, a_{w})$ for all vertices $w$ on the path from $u$ to $v$. As it might be large, compute it modulo $10^9+7$. Here $gcd(s, t)$ denotes the greatest common divisor of $s$ and $t$.\n\nNote that the numbers in vertices **do not** change after queries.\n\nI suppose that you are more interested in superhero business of Thanos and Dr. Strange than in them solving the problem. So you are invited to solve this problem instead of them.\n\n## Input\n\nIn the first line of input there is one integer $n$ ($1 \\le n \\le 10^{5}$) — the size of the tree.\n\nIn the next $n-1$ lines the edges of the tree are described. The $i$\\-th edge is described with two integers $u_{i}$ and $v_{i}$ ($1 \\le u_{i}, v_{i} \\le n$) and it connects the vertices $u_{i}$ and $v_{i}$. It is guaranteed that graph with these edges is a tree.\n\nIn the next line there are $n$ integers $a_1, a_2, \\ldots, a_n$ ($1 \\le a_{v} \\le 10^{7}$).\n\nIn the next line there is one integer $q$ ($1 \\le q \\le 10^{5}$) — the number of queries.\n\nAnd in the next $q$ lines the queries are described. Each query is described with three integers $u_{i}$, $v_{i}$ and $x_{i}$ ($1 \\le u_{i}, v_{i} \\le n$, $1 \\le x_{i} \\le 10^{7}$).\n\n## Output\n\nPrint $q$ numbers — the answers to the queries in the order they are given in the input. Print each answer modulo $10^9+7 = 1000000007$. Print each number on a separate line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"设本题的主要角色来自某部近期电影中的角色。新《复仇者联盟》似乎引起了大量关注。我从未看过该系列的任何部分，也不太了解其英雄，但这不妨碍我在本题题面中使用他们。因此，灭霸和奇异博士正在做他们的超级英雄和超级反派的事情，但突然间他们遇到了一个普通的竞赛编程问题。\n\n给你一棵包含 $n$ 个顶点的树。\n\n在每个顶点 $v$ 中有一个正整数 $a_v$。\n\n你需要回答 $q$ 个查询。\n\n每个查询的形式为 $u$ $v$ $x$。\n\n你需要计算 $\\prod_{w \\in P} \\gcd(x, a_w) \\mod (10^9 + 7)$，其中 $P$ 是从 $u$ 到 $v$ 的路径上的顶点集合。换句话说，你需要计算路径上所有顶点 $w$ 的 $\\gcd(x, a_w)$ 的乘积。由于结果可能很大，请对 $10^9 + 7$ 取模。这里 $\\gcd(s, t)$ 表示 $s$ 和 $t$ 的最大公约数。\n\n注意，顶点中的数字在查询后 *不会* 改变。\n\n我想你对灭霸和奇异博士的超级英雄事务比对他们解题更感兴趣。因此，邀请你代替他们来解决这个问题。\n\n输入的第一行包含一个整数 $n$ ($1 \\leq n \\leq 10^5$) —— 树的大小。\n\n接下来的 $n - 1$ 行描述了树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ ($1 \\leq u_i, v_i \\leq n$) 描述，表示连接顶点 $u_i$ 和 $v_i$。保证这些边构成的图是一棵树。\n\n下一行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 \\leq a_v \\leq 10^7$)。\n\n下一行包含一个整数 $q$ ($1 \\leq q \\leq 10^5$) —— 查询的数量。\n\n接下来的 $q$ 行描述查询。每个查询由三个整数 $u_i$, $v_i$ 和 $x_i$ ($1 \\leq u_i, v_i \\leq n$, $1 \\leq x_i \\leq 10^7$) 描述。\n\n请输出 $q$ 个数 —— 按输入顺序输出每个查询的答案。每个答案对 $10^9 + 7 = 1000000007$ 取模。每个数单独占一行。\n\n## Input\n\n在输入的第一行包含一个整数 $n$ ($1 \\leq n \\leq 10^5$) —— 树的大小。接下来的 $n - 1$ 行描述了树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ ($1 \\leq u_i, v_i \\leq n$) 描述，表示连接顶点 $u_i$ 和 $v_i$。保证这些边构成的图是一棵树。下一行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 \\leq a_v \\leq 10^7$)。下一行包含一个整数 $q$ ($1 \\leq q \\leq 10^5$) —— 查询的数量。接下来的 $q$ 行描述查询。每个查询由三个整数 $u_i$, $v_i$ 和 $x_i$ ($1 \\leq u_i, v_i \\leq n$, $1 \\leq x_i \\leq 10^7$) 描述。\n\n## Output\n\n请输出 $q$ 个数 —— 按输入顺序输出每个查询的答案。每个答案对 $10^9 + 7 = 1000000007$ 取模。每个数单独占一行。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ T = (V, E) $ be a tree with $ |V| = n $, and let $ a: V \\to \\mathbb{Z}^+ $ be a function assigning a positive integer $ a_v $ to each vertex $ v \\in V $.\n\nFor each query $ (u, v, x) $, let $ P_{u,v} $ denote the set of vertices on the unique simple path from $ u $ to $ v $ in $ T $.\n\nThe answer to the query is:\n$$\n\\prod_{w \\in P_{u,v}} \\gcd(x, a_w) \\mod (10^9 + 7)\n$$\n\nGiven:\n- $ 1 \\leq n, q \\leq 10^5 $\n- $ 1 \\leq a_v, x \\leq 10^7 $\n- The tree is undirected and connected.\n\nCompute the answer for each of the $ q $ queries modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF986E","tags":["brute force","data structures","math","number theory","trees"],"sample_group":[["4\n1 2\n1 3\n1 4\n6 4 9 5\n3\n2 3 6\n2 3 2\n3 4 7","36\n4\n1"],["6\n1 2\n2 3\n2 4\n1 5\n5 6\n100000 200000 500000 40000 800000 250000\n3\n3 5 10000000\n6 2 3500000\n4 1 64000","196000\n12250\n999998215"]],"created_at":"2026-03-03 11:00:39"}}