- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
کِوین از کودکی علاقهی زیادی به اعداد باینری (صفر و یکی) داشتهاست، این داستان یکی از کارهایی است که او با آنها میکردهاست.
اگر رشته باینری را به صورت
\(s_1,s_2,...,s_n\)
نشاندهیم و \(n\) برابر طول آن باشد، زیبایی رشته برابر تعداد ۴ تاییهای
\(s_i,s_j,s_k,s_l\)
که هر کدام یک بیت (یا صفر یا یک است) از رشتهاند که
\(1\le i کوِین به شما رشتهی باینری \(s\) را دادهاست، زیبایی آن را بدست آورید. به دلیل این که زیبایی رشتهی \(s\) میتواند زیاد باشد. باقیماندهی تقسیم زیبایی آن را بر \( 10^9+7 \) چاپ کنید. برای آشنایی با عملگرهای بیتی اینجا را بخوانید. در تنها خط ورودی رشتهی \(s\) داده میشود.
دقت کنید که \(s\) میتواند با صفر شروع شود.
\[4 \le |s| \le 500 \ 000\] منظور از \(|s|\) طول رشتهی \(s\) است. در تنها خط خروجی باقیماندهی تقسیم زیبایی رشتهی \(s\) را بر \( 10^9+7 \) را چاپ کنید. توضیح: چهارتاییهای
\(s_1,s_3,s_4, s_6\)
و چهار تایی
\(s_1,s_3,s_5,s_6\)
معتبر اند.ورودی
خروجی
مثال
ورودی نمونه ۱
1010101
خروجی نمونه ۱
2
ورودی نمونه ۲
01100100
خروجی نمونه ۲
10