BW-M4. Qism to‘plamlar XORi

n ta son berilgan. Ularning barcha 2ⁿ qism to‘plamini (bo‘sh to‘plam ham — uning XORi 0) ko‘rib chiqamiz va har birining XORini hisoblaymiz. Shu XORlar yig‘indisini 10⁹ + 7 ga bo‘lgandagi qoldiqni toping.

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida n ta son.

Chiqish ma’lumotlari

Bitta son — yig‘indi mod 10⁹ + 7.

Cheklovlar

1 ≤ n ≤ 2·10⁵; 0 ≤ aᵢ ≤ 10⁹.