В стране Древляндии есть $$$N$$$ городов, каждый из которых имеет номер от $$$1$$$ до $$$N$$$. Также известно, что между некоторыми из городов имеются двунаправленные дороги, к тому же из каждого города можно добраться до любого другого единственным способом, возможно, проезжая через другие города. Помимо этого, за проезд по дороге нужно заплатить определенное количество денег. Коммивояжеру Алексею предстоит совершить $$$Q$$$ поездок между парами городов и для каждой он хочет узнать, сколько денег ему придётся потратить в каждой из поездок. Однако стоимость проезда рассчитывается по очень странной формуле: все стоимости проезда перемножаются, а затем полученный результат берётся по модулю $$$10^9 + 7$$$. Так как Алексей очень плохо умеет считать, он просит вас помочь ему. Ваша задача – написать программу, которая для каждой поездки Алексея посчитает её стоимость.