Циншань и Даниэль собираются сыграть в карточную игру. Но играть в нее только вдвоем будет очень скучно. Поэтому они решили сделать \(n\) роботов, чтобы они сыграли в игру автоматически. Роботы, сделанные Циншань, относятся к команде \(1\), а роботы, сделанные Даниэлем, относятся к команде \(2\). Робот \(i\) находится в команде \(t_i\). Перед началом игры роботу \(i\) выдается \(a_i\) карт.
Правила карточной игры просты:
- Роботы выстраиваются по кругу в порядке номеров и будут в некотором порядке выбрасывать по одной карте. Сначала робот \(1\) выбрасывает одну из своих карт из игры. После этого роботы будут действовать по следующим правилам:
- Если последнюю карту выбросил робот \(i\), то следующим карту выбрасывает ближайший робот, чья команда противоположна команде \(i\)-го робота. Другими словами, робот \(j\) должен выбросить одну свою карту сразу после робота \(i\), если и только если среди всех возможных \(j\) таких, что \(t_i\ne t_j\), расстояние \(dist(i,j)\) (определение будет дано ниже) минимально.
- Робот, у которого больше не осталось карт, должен завершить игру немедленно. Этот робот не будет рассматриваться в следующих шагах.
- Когда нет подходящего робота, который должен выбросить следующую карту, игра заканчивается.
Мы определяем расстояние от робота \(x\) до робота \(y\) как \(dist(x,y)=(y-x+n)\bmod n\). Это соответствует ориентированному расстоянию по кругу.
Например, если \(n=5\), то расстояние от \(1\) до \(3\) это \(dist(1,3)=(3-1+5)\bmod 5=2\), а расстояние от \(3\) до \(1\) это \(dist(3,1)=(1-3+5)\bmod 5 =3\).
Циншань заметила, что наблюдение за игрой роботов занимает очень большое время. Она хочет узнать результаты как можно быстрее. Вы, как фанат Циншань, должны помочь ей посчитать массив \([ans_1,ans_2,\ldots,ans_n]\): \(ans_i\) равно количеству карт, которое выбросит \(i\)-й робот в течение всей игры. Нужно спешить!
Чтобы избежать большого размера входных данных, команды и количества карт каждого робота должны быть сгенерированы в вашей программе с использованием некоторых вспомогательных массивов.
Выходные данные
Выведите единственное целое число \(\left( \prod_{i=1}^{n} ((ans_i \oplus i^2)+1)\right) \bmod 10^9+7\), где \(\oplus\) обозначает операцию исключающего ИЛИ.
Примечание
В первом тесте \(a=[5,5,1]\) и \(t=[1,2,2]\).
Робот \(1\) выбрасывает первую карту.
Затем робот \(2\) выбрасывает карту. Это делает не робот \(3\), потому что \(dist(1,2)<dist(1,3)\).
Затем робот \(1\) выбрасывает карту. Это делает не робот \(3\), потому что \(t_2=t_3\).
Если мы выпишем индексы роботов, которые будут выбрасывать карты по очереди, то мы получим последовательность \([1,2,1,2,1,2,1,2]\). Поэтому роботы \(1\), \(2\) и \(3\) уберут \(5\), \(5\) и \(0\) карт, соответственно. Ответ будет равен \((((5 \oplus 1^2)+1)\times((5 \oplus 2^2)+1)\times((0 \oplus 3^2)+1)) \bmod 10^9+7=(5\times 2 \times 10)\bmod 10^9+7=100\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 5 2 3
2 7 1 2
3 2 1 1
|
100
|
|
2
|
5000000
2
1919810 998244353 114514 19260817
5000000 233333333 623532 7175
|
800210675
|
|
3
|
1
1
1 1 0 0
|
1
|