D. Дреамүүн ба Хоёртын тооллын систем

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

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

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

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

Дреамүүн газар дээр нэгэн том бүхэл тоо $x$ бичигдсэн байхыг хараад үүнийг хоёртын тооллын системд бичихийг хүсжээ. Дреамүүн $x$-ыг хоёртын тоолол болгох хэсгийг нь хийчихсэн. Одоо тэрээр дараах байдлаар хэвлэх хэрэгтэй.

Түүнд бүхэл тоо $n = 0$ байна. Мөн тэрээр дараах 2 үйлдлийг алийг нь ч, ямар ч дараалалтайгаар, хязгааргүй удаа гүйцэтгэж чадна:

  1. n-ийг 0-ээр эхлээгүй 2-тын тооллын системд хэвлэх. Хэвлэлт болгон өмнөх хэвлэлтийн баруун талд нь нэмж хэвлэгдэнэ.
  2. n-ийг 1-ээр нэмэгдүүлнэ.

$x$-ыг 0-ээр эхлээгүй 2-тын тооллын системд оруулах үйлдлүүдийн дарааллыг төгс дараалал гэж нэрлэе. Дреамүүн нийт хэдэн ялгаатай төгс дараалал байгаа болон хамгийн богинохон төгс дарааллын уртыг мэдмээр байгаа болно.

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

Төгс дарааллыг $'1'$, $'2'$ гэсэн тэмдэгтүүдээс бүтсэн тэмдэгт мөр гэж тодорхойльё (Энд $i$ дэхь тэмдэгт нь $i$ дэхь үйлдлийг илэрхийлнэ). Хэрвээ 2 төгс дарааллын тэмдэгт мөр нь хоорондоо ялгаатай бол энэ 2 тэмдэгт мөрийг ялгаатай гэж үзнэ.

Оролт

Нэг мөрөнд $x$ ($1 ≤ x < 2^{5000}$)-ийн хоёртын тоолол дахь тоо болох нэг бүхэл тоо өгөгдөнө.

Гаралт

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

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

Орчуулсан: Энхлут

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

Оролт
101
Гаралт
1
6
Оролт
11010
Гаралт
3
5

Тэмдэглэл

Эхний жишээнд хамгийн богино болон цор ганц төгс дараалал нь $6$ урттай «$222221$» дараалал юм.

2 дахь жишээнд 3-н төгс дараалал «$21211$», «$212222222221$», «$222222222222222222222222221$» байгаа. Эдгээрийн хамгийн богино урт нь $5$ юм.

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