Віслюк, Шрек і Кіт у чоботях пробралися до зіллєварні Хрещеної феї, щоб знайти зілля, яке вирішить шлюбні проблеми огра. Однак вони не змогли знайти таке зілля, тому їм доведеться зварити його самостійно.
У зіллєварні є зіль, при цьому -те зілля має міцність a_i. Їм потрібно обрати деяку непорожню підмножину зіль, щоб зварити їх разом і створити гарне зілля. Нове зілля матиме наступні характеристики:
Його солодкість, яка розраховується як побітова операція XOR усіх міцностей зіль, які варять.
Його аромат, який розраховується як побітова операція AND усіх міцностей зіль, які варять.
Його тривалість, яка розраховується як побітова операція OR усіх міцностей зіль, які варять.
Зілля вважається вдалим тоді й тільки тоді, коли сума його солодкості та аромату дорівнює його тривалості. Вам потрібно визначити кількість способів, якими Шрек і його друзі можуть зварити вдале зілля.
Іншими словами, знайдіть кількість непорожніх підпослідовностей з , для яких виконується \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.
Приклад
У першому прикладі, зварити вдале зілля можна взявши такі підмножини зілль: , , , , , , , , , та \{1,2,4\}; Сумарно це способів. Наприклад, якщо ми візьмемо множину \{1,2,4\}, побітова операція OR рівний , побітова операція AND рівна , а побітова операція XOR рівна , оскільки 0+7=7, то це зілля є справді вдалим.