Задача №115243. Случай в казино
Оушен и друзья решили ограбить казино, играя в автоматы. Всего в казино есть \(n\) игровых автоматов, если сыграть на \(i\)-м автомате, то выигрыш составит \(a_{i}\) рублей.
Оушен взломал систему и знает, что выиграет на каждом автомате с первой попытки, но ровно один раз. Оушен очень жадный, поэтому он точно сыграет ровно один раз на каждом автомате.
При этом система безопасности казино считает подозрительным ситуацию, когда игрок выиграл один или несколько раз на автоматах и суммарный выигрыш игрока делится на \(3\). Математик из команды Оушена хочет найти количество способов выбрать порядок автоматов, чтобы сыграть на каждом автомате ровно один раз, и остаться не замеченным системой безопасности. Поскольку способов может быть очень много, выведите остаток от деления количества способов на \(10^{9} + 7\).
В первой строке дано одно натуральное число \(n\) — количество автоматов в казино (\(1 \le n \le 10^{5}\)).
Вторая строка содержит \(n\) целых чисел \(a_{1}, a_{2}, \ldots, a_{n}\) (\(1 \le a_{i} \le 10^{9}\)).
Выведите единственное целое число — взятое по модулю \(10^{9} + 7\) количество способов сыграть на каждом автомате ровно один раз, ни в какой момент не имея положительный суммарный выигрыш, кратный \(3\).
3 100 21 892
4
4 11 19 30 32
6
3 4 298 28
0