• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

کِوین از کودکی علاقه‌ی زیادی به اعداد باینری (صفر و یکی) داشته‌است، این داستان یکی از کار‌هایی است که او با آن‌ها می‌کرده‌است.

اگر رشته باینری را به صورت $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$ چاپ کنید.

برای آشنایی با عملگر‌های بیتی اینجا را بخوانید.

ورودی

در تنها خط ورودی رشته‌ی $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