В королевстве Осени $$$n$$$ городов, пронумерованных от $$$1$$$ до $$$n$$$. От любого города можно добраться до любого другого, используя некоторые из $$$n-1$$$ дорог в королевстве.

В этом году правительство приняло решение разбить королевство на регионы. После разбиения будут существовать регионы нескольких уровней, при этом само королевство будет являться регионом первого уровня. Любой регион уровня $$$i$$$ должен быть разделен на несколько (хотя бы два) регионов уровня $$$i+1$$$, если это не регион последнего уровня. Каждый город должен принадлежать ровно одному региону каждого уровня. Внутри одного региона, между любыми двумя городами в нем должен существовать путь, проходящий только по городам этого региона.

Согласно исследованию, для каждого города $$$i$$$ есть уровень важности — $$$a_i$$$. Все регионы одного уровня должны иметь одинаковую сумму этих значений.

Ваша задача состоит в том, чтобы узнать, сколько существует планов разбиения королевства на регионы, чтобы все условия выполнялись. Два плана считаются различными тогда и только тогда, когда количество уровней в них различно, или существует пара городов, которые для какого-то уровня находятся в одном регионе в одном плане, но в разных регионах того же уровня в другом. Поскольку ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$.