Віслюче, стій на варті#12978

Віслюче, стій на варті

4 секунди
512 мегабайтів
Дуже складна

Віслюк, Шрек і Кіт у чоботях пробралися до зіллєварні Хрещеної феї, щоб знайти зілля, яке вирішить шлюбні проблеми огра. Однак вони не змогли знайти таке зілля, тому їм доведеться зварити його самостійно.

У зіллєварні є зіль, при цьому -те зілля має міцність a_i. Їм потрібно обрати деяку непорожню підмножину зіль, щоб зварити їх разом і створити гарне зілля. Нове зілля матиме наступні характеристики:

Зілля вважається вдалим тоді й тільки тоді, коли сума його солодкості та аромату дорівнює його тривалості. Вам потрібно визначити кількість способів, якими Шрек і його друзі можуть зварити вдале зілля.

Іншими словами, знайдіть кількість непорожніх підпослідовностей з , для яких виконується \text{XOR}(s)+\text{AND}(s)=\text{OR}(s).

Вхідні дані

У першому рядку задано одне ціле число — кількість доступних зілль.

У другому рядку задано цілих чисел — міцності зілль.

1\leq n\leq 10^6,

0\leq a_i \leq 15 \cdot 10^3.

Вихідні дані

Виведіть одне ціле число — кількість способів зварити вдале зілля. Оскільки відповідь може бути дуже велика виведіть її за модулем 10^9+7.

Приклади

Приклад

Loading
Loading

Примітка

У першому прикладі, зварити вдале зілля можна взявши такі підмножини зілль: , , , , , , , , , та \{1,2,4\}; Сумарно це способів. Наприклад, якщо ми візьмемо множину \{1,2,4\}, побітова операція OR рівний , побітова операція AND рівна , а побітова операція XOR рівна , оскільки 0+7=7, то це зілля є справді вдалим.