Боулінг аналіз#5869
Гра Боулінг має такі правила: на прямій стоїть ряд з кеглів. Відстань між двома сусідніми кеглями дорівнює . Гравці ходять по черзі. За один хід гравець може збити одну кеглю або дві, відстань між якими дорівнює . Промахуватись не можна. Виграє той, хто збив останню кеглю.
У нашому випадку все трохи складніше. Вован і Петян — два бізнесмени, які орендували цілий кегельбан. В їхньому розпорядженні незалежних доріжок для боулінгу. Під час свого ходу гравець вибирає, на якій доріжці зробити хід, і виконує його. Далі інший гравець може вибрати іншу або ту ж саму доріжку. І так далі. Умова перемоги залишається: збити останню кеглю.
Вован ходить першим, і йому цікаво дізнатись, скільки у нього є різних виграшних ходів. Два ходи вважаються різними, якщо хоча б одна кегля, збита під час одного ходу, не збита під час іншого або навпаки.
Перший рядок містить кількість доріжок (n \leq 1000). Другий рядок містить натуральних чисел k_i (k_i \leq 1000) — кількість кеглів на доріжці номер .
Виведіть кількість виграшних ходів Вована.
Приклад 1
Приклад 2