搬题人提示：本题数据由 Deekseek 辅助生成，数据总大小约为 405 MB，请使用一些较为快速的 IO 方式。
大厨住在一个叫大厨国的国度中。这个国家可以表示成一棵包含 个城市（编号为 ），由 条道路相连的树。对每个合法的 ，第 座城市的房价为 。
你需要回答 个询问。
在每个询问中，你会得到两个城市 和 （可能相等），大厨打算在这两个城市买房子。
大厨的幸福感程度等于从 到 （包括 ）的简单路径上所有城市的房价之积。
由于大厨喜欢约数，他希望告诉你，他的幸福程度的约数个数，对 （）取模后输出。
