Действующими лицами этой задачи будут герои какого-нибудь недавно вышедшего в прокат фильма. Кажется, в последнее время много мемов по «Мстители: Война бесконечности». Я не смотрел ни одной части, поэтому лишь смутно знаю героев. Впрочем, это не помешает мне использовать их в задаче. Пусть героями нашей задачи будут Танос и Доктор Стрендж. Итак, Танос и Доктор Стрендж занимаются своими супергеройскими и суперзлодейскими делами, как вдруг они наталкиваются на обычную задачу по спортивному программированию.
Есть дерево размера \(n\).
В каждой вершине \(v\) записано целое положительное число \(a_{v}\).
Нужно ответить на \(q\) запросов.
Запрос задаётся в виде \(u\) \(v\) \(x\).
Нужно посчитать \(\prod_{w \in P} gcd(x, a_{w}) \mod (10^{9} + 7)\), где \(P\) — множество вершин, лежащих на пути из \(u\) в \(v\). Иными словами, вычислите произведение \(gcd(x, a_{w})\) для всех вершин \(w\) на пути от \(u\) до \(v\). Так как произведение может быть большим, выведите его по модулю \(10^9+7\). Здесь \(gcd(s, t)\) обозначает наибольший общий делитель \(s\) и \(t\).
Обратите внимание, что сами числа в вершинах не изменяются.
Думаю, вам интереснее было бы смотреть на супергеройские похождения Доктора Стренджа и Таноса, чем на то, как они решают задачку. Поэтому вам предлагается решить задачу вместо них.