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

Обмеження: 4 сек., 512 МіБ

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

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

• Його солодкість, яка розраховується як побітова операція XOR усіх міцностей зіль, які варять.

• Його аромат, який розраховується як побітова операція AND усіх міцностей зіль, які варять.

• Його тривалість, яка розраховується як побітова операція OR усіх міцностей зіль, які варять.

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

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

Вхідні дані

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

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

Вихідні дані

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

Обмеження

\(1\leq n\leq 10^6\),

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 2 3 4 5	11

Примітки

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