D. Жууху ба тоонууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жуухуд $n$ ширхэг сөрөг биш $a_{1}, a_{2}, ..., a_{n}$ бүхэл тоонууд байна. Бид $i_{1}, i_{2}, ..., i_{k}$ $(1 ≤ i_{1} < i_{2} < ... < i_{k} ≤ n)$ дугааруудын дарааллыг $k$ хэмжээтэй бүлэг гэж дуудна.

Жууху $a_{i_{1}}$ & $a_{i_{2}}$ & ... & $a_{i_{k}} = 0$ $(1 ≤ k ≤ n)$ байх хэдэн бүлэг байгаа бол гэж бодож байгаа бол түүнд үүнийг тооцоолж олоход нь тусална уу. Тооцоолж олсон тооны $1000000007$ $(10^{9} + 7)$-д хуваасан үлдэгдлийг хэвлэнэ үү.

($x \& y$ нь хоёр тооны хоорондох битийн AND үйлдлийг илэрхийлнэ)

Оролт

Эхний мөр нь нэг бүхэл $n$ $(1 ≤ n ≤ 10^{6})$ тоог агуулна. Хоёр дахь мөр нь $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ $(0 ≤ a_{i} ≤ 10^{6})$ бүхэл тоонуудыг агуулна.

Гаралт

Нэг мөрөнд шаардлага хангах бүлгүүдийн тоог $1000000007$ $(10^{9} + 7)$-д хуваасан үлдэгдлийг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3
2 3 3
Гаралт
0
Оролт
4
0 1 2 3
Гаралт
10
Оролт
6
5 2 0 5 2 1
Гаралт
53
Сэтгэгдлүүдийг ачааллаж байна...