SuperNim Junior

Нім — це гра для двох гравців, які по черзі забирають предмети, розподілені на декілька куп. На кожному ході гравець вибирає непорожню купу і забирає з неї будь-яку ненульову кількість предметів. Гравець, який не може зробити хід під час свого ходу (тобто, коли його суперник зробив останній хід і забрав останній предмет), програє.

Ця гра була повністю математично проаналізована. Програшні позиції — це такі позиції, з яких незалежно від ходу гравця суперник завжди може відповісти так, що врешті-решт виграє (тобто, у суперника є виграшна стратегія). Виграшні позиції — це ті, з яких незалежно від гри суперника гравець, який ходить, завжди може відповідати так, щоб у підсумку перемогти (тобто, у цього гравця є виграшна стратегія).

Відомо, що виграшність позиції визначається ним-сумою:

де p_i — кількість предметів у $i$-й купі, а $\text{xor}$ позначає бітову операцію виключного АБО (тобто додавання в бінарній системі без перенесень). Якщо ним-сума ненульова, позиція виграшна; якщо рівна нулю — програшна.

У цій задачі вам задано дуже велику кількість куп. Ваше завдання: знаючи розміри куп, визначити кількість способів для першого гравця зробити перший хід із початкової позиції так, щоб у нього залишилася виграшна стратегія (тобто, після цього ходу перший гравець залишиться у виграшній позиції).