A. Малек бүжгийн клуб

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

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

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

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

Уламжлал ёсоор жил бүр ОУПО-ийн өмнө Наталиагийн шүтэн бишрэгчдийн клубын гишүүд Малек Бүжгийн Клубт шөнөжин хөгжилдөхөөр уригддаг байна. Малек бүжгийн клуб $2^{n}$ гишүүнтэй ба Наталиагийн шүтэн бишрэгчдийн клуб мөн $2^{n}$ гишүүнтэй байна. МБК-ийн гишүүн бүр $0$-ээс $2^{n} - 1$ хүртэлх ялгаатай дугаартай. НШБК-ийн гишүүд мөн адилхан.

Энэхүү уламжлалд МБК-ийн гишүүн бүр НШБК-ийн нэг гишүүнтэй хослон бүжиглэдэг байна. Хос бүжигчдийг $(a, b)$ гэж тэмдэглэх ба $a$ нь МБК-ийн гишүүн ба $b$ нь НШБК-ийн гишүүн байна.

$a < c$ ба $b > d$ байх $(a, b)$ ба $(c, d)$ хосуудын тоог хуваарилалтын цогцлол гэж нэрлэе.

Чамд $n$ урттай хоёртын $x$ гэсэн тоо өгөгдөнө. Бид МБК-ийн $i$ дугаарын гишүүн НШБК-ийн дугаарын гишүүнтэй бүжиглэхийг мэдэж байгаа. Чиний даалгавар бол энэхүү хуваарилалтын цогцлолыг олж $1000000007$ $(10^{9} + 7)$ тоонд хуваан үлдэгдлийг олох юм.

илэрхийллээр $x$ ба $y$ тоонууд дээр «XOR» үйлдлийг тэмдэглэв. Энэхүү үйлдэл нь орчин үеийн бүхий л програмчлалын хэлд байгаа. Тухайлбал $C++$ ба $Java$ хэлэнд «$^$» гэж, харин $Pascal$ хэлэнд «$xor$» гэж тэмдэглэнэ.

Оролт

Эхний мөрөнд $n$ урттай $x$ гэсэн хоёртын тоо өгөгдөнө $(1 ≤ n ≤ 100)$.

Уг тоо тэгээр эхэлсэн байж болно.

Гаралт

Өгөгдсөн хуваарилалтын цогцлолыг олж $1000000007$ $(10^{9} + 7)$ тоонд хуваан үлдэгдлийг хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
11
Гаралт
6
Оролт
01
Гаралт
2
Оролт
1
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...