Masala #3LXXUSZXZP

Xotira 256 MB Vaqt 2000 ms

Binar satrni almashtirish

Shohruhda \(0\) va \(1\) dan tashkil topgan binar satri mavjud. Bir amalda satrdagi ixtiyoriy \(01\) qism-satrini tanlab uni \(110\) ga o'zgartirish mumkin. Satrda \(01\) satri qolmasligi uchun yuqoridagi amaldan eng kamida necha marotaba foydalanish kerakligini aniqlang. Natija juda katta bo'lishi mumkin, shuning uchun uni \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining yagona qatorida \(s(|s| \le 10^5)\) satri kiritiladi.

Chiquvchi ma'lumotlar:

Minimum amallar sonini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.

Misollar

#	input.txt	output.txt
1	101	1
2	0101	4