В королевстве Осени \(n\) городов, пронумерованных от \(1\) до \(n\). От любого города можно добраться до любого другого, используя некоторые из \(n-1\) дорог в королевстве.
В этом году правительство приняло решение разбить королевство на регионы. После разбиения будут существовать регионы нескольких уровней, при этом само королевство будет являться регионом первого уровня. Любой регион уровня \(i\) должен быть разделен на несколько (хотя бы два) регионов уровня \(i+1\), если это не регион последнего уровня. Каждый город должен принадлежать ровно одному региону каждого уровня. Внутри одного региона, между любыми двумя городами в нем должен существовать путь, проходящий только по городам этого региона.
Согласно исследованию, для каждого города \(i\) есть уровень важности — \(a_i\). Все регионы одного уровня должны иметь одинаковую сумму этих значений.
Ваша задача состоит в том, чтобы узнать, сколько существует планов разбиения королевства на регионы, чтобы все условия выполнялись. Два плана считаются различными тогда и только тогда, когда количество уровней в них различно, или существует пара городов, которые для какого-то уровня находятся в одном регионе в одном плане, но в разных регионах того же уровня в другом. Поскольку ответ может быть очень большим, выведите его по модулю \(10^9+7\).
Примечание
В первом примере существует \(4\) различных плана:
План \(1\): Уровень \(1\): \(\{1,2,3,4\}\).
План \(2\): Уровень \(1\): \(\{1,2,3,4\}\), Уровень \(2\): \(\{1,2\}\),\(\{3,4\}\).
План \(3\): Уровень \(1\): \(\{1,2,3,4\}\), Уровень \(2\): \(\{1\}\),\(\{2\}\),\(\{3\}\),\(\{4\}\).
План \(4\): Уровень \(1\): \(\{1,2,3,4\}\), Уровень \(2\): \(\{1,2\}\),\(\{3,4\}\), Уровень \(3\): \(\{1\}\),\(\{2\}\),\(\{3\}\),\(\{4\}\).
Во втором примере существует \(2\) различных плана:
План \(1\): Уровень \(1\): \(\{1,2,3,4\}\).
План \(2\): Уровень \(1\): \(\{1,2,3,4\}\), Уровень \(2\): \(\{1\}\),\(\{2\}\),\(\{3\}\),\(\{4\}\).
В третьем примере существует \(3\) различных плана:
План \(1\): Уровень \(1\): \(\{1,2,3,4\}\).
План \(2\): Уровень \(1\): \(\{1,2,3,4\}\), Уровень \(2\): \(\{1,2\}\),\(\{3,4\}\).
План \(3\): Уровень \(1\): \(\{1,2,3,4\}\), Уровень \(2\): \(\{1,3\}\),\(\{2\}\),\(\{4\}\).