Танд $n$ ширхэг бүхэл тоонууд $a_{1},  a_{2},  ...,  a_{n}$-ууд өгөгдөв.

Бүхэл тоонуудын дараалал $x_{1},  x_{2},  ...,  x_{k}$-ын хувьд хэрэв $1  ≤  i  ≤  k - 1$ бүрийн хувьд $x_{i}$ тооны 2-тын бичлэг доторх 1-ийн тоо $x_{i  +  1}$ тооны 2-тын бичлэг доторх 1-ийн тоо гэсэн утга нь $3$-т хуваагдах бөгөөд бүх $1 ≤ i ≤ k$ -ын хувьд байвал уг дарааллыг "xor-дараалал" хэмээн нэрлэх ажээ. гэсэн тэмдэг нь 2-тын тооллын систем дэх or үйлдлийг илэрхийлнэ.

Тэгвэл $k$ урттай хэчнээн ширхэг "xor-дараалал" оршин байгаа вэ? Бодлогын хариултыг $10^{9} + 7$ модулаар бодож хэвлэнэ үү.

Хэрэв $a = [1, 1]$ ба $k = 1$ байвал бодлогын хариулт нь $2$ байхыг анхаарна уу. Учир нь та $a$ дотор байгаа 1-үүдийг ялгаатай гэж үзэх ёстой юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 100$, $1 ≤ k ≤ 10^{18}$) өгөгдөх ба эдгээр нь танд өгөгдөх бүхэл тоонуудын тоо болон "xor-дараалал"-уудын уртыг илэрхийлнэ.

2-дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{i}$ ($0 ≤ a_{i} ≤ 10^{18}$)-ууд өгөгдөнө.

Гаралт

$k$ урттай "xor-дараалал"-уудын тоог $10^{9} + 7$ модулаар бодсон утга болох ганц бүхэл тоо $c$-г хэвлэнэ үү.