+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- > *کِوین* از کودکی علاقه‌ی زیادی به اعداد باینری (صفر و یکی) داشته‌است، این داستان یکی از کار‌هایی است که او با آن‌ها می‌کرده‌است. اگر رشته باینری را به صورت $s_1,s_2,...,s_n$ نشان‌دهیم و $n$ برابر طول آن باشد، *زیبایی* رشته برابر تعداد ۴ تایی‌های $s_i,s_j,s_k,s_l$ که هر کدام یک **بیت** (یا صفر یا یک است) از رشته‌اند که $1\le i<j<k<l \le n$ و $$ s_i \ and \ s_j \; = \; s_j \ or \ s_k \; = \; s_k \ nand \ s_l \; = \; s_l \ xor \ s_i $$ است. *کوِین* به شما رشته‌ی باینری $s$ را داده‌است، *زیبایی* آن را بدست آورید. به دلیل این که *زیبایی* رشته‌ی $s$ می‌تواند زیاد باشد. باقی‌مانده‌ی تقسیم *زیبایی* آن را بر $ 10^9+7 $ چاپ کنید. برای آشنایی با عملگر‌های بیتی [اینجا](https://fa.wikipedia.org/wiki/%D8%AC%D8%AF%D9%88%D9%84_%D8%A7%D8%B1%D8%B2%D8%B4) را بخوانید. # ورودی در تنها خط ورودی رشته‌ی $s$ داده می‌شود. دقت کنید که $s$ می‌تواند با صفر شروع شود. $$4 \le |s| \le 500 \ 000$$ منظور از $|s|$ طول رشته‌ی $s$ است. # خروجی در تنها خط خروجی باقی‌مانده‌ی تقسیم *زیبایی* رشته‌ی $s$ را بر $ 10^9+7 $ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1010101 ``` ## خروجی نمونه ۱ ``` 2 ``` توضیح: چهار‌تایی‌ها‌ی $s_1,s_3,s_4, s_6$ و چهار تایی $s_1,s_3,s_5,s_6$ معتبر اند. ## ورودی نمونه ۲ ``` 01100100 ``` ## خروجی نمونه ۲ ``` 10 ```

حل سؤال در بانک سؤالات