D. Үнэг ба төгс олонлогууд

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

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

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

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

Үнэг Сиел тооны онолыг судалсан байна.

Тэр хоосон биш $S$ олонлог сөрөг биш бүхэл тоонуудаас бүрддэг ба хэрвээ ямар ч ($a$ нь $b$-тэй тэнцүү байж болно), бол төгс олонлог гэж боддог.

$xor$ үйлдэл нь үл зохицох эсвэл ($http://en.wikipedia.org/wiki/Exclusive_or$) үйлдлийг илэрхийлнэ.

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

Оролт

Нэг мөрөнд $k$ ($0 ≤ k ≤ 10^{9}$) бүхэл тоог оруулна.

Гаралт

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

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

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

Оролт
1
Гаралт
2
Оролт
2
Гаралт
3
Оролт
3
Гаралт
5
Оролт
4
Гаралт
6

Тэмдэглэл

Жишээ 1, 2 олонлог байна: {0} aба {0, 1}. {1} бол гайхалтай олонлог биш гэдгийг анхаарна уу, учир нь 1 xor 1 = 0 ба {1} тэг агуулагүй.

Жишээ 4, 6 олонлог байна: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 1, 2, 3}.

Сэтгэгдлүүдийг ачааллаж байна...