مرد مالیاتچی و جاعل


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

اخیرا جاعلی پیدا شده است که فیش جعلی پرداخت مالیات درست می‌کند. با این روش مردم یک فیش جعلی، که نشان می‌دهد آن‌ها مالیاتشان را پرداخته‌اند، از این جاعل می‌گیرند و به اداره‌ی مالیات نشان‌ می‌دهند و دیگر مالیات نمی‌دهند. این پدیده‌ی شوم باعث کسادی بازار مرد مالیاتچی و بیکاری او شده است. متاسفانه مرد مالیاتچی که نمی‌تواند جلوی این اتفاق را بگیرد می‌خواهد بداند که حداقل چقدر وقتش خالی شده‌ است تا بتواند شغل دوم مناسبی پیدا کند. از این رو میخواهد تعداد فیش‌های اصل را بداند.

یک فیش مالیاتی رشته‌ای به طول nn است که تنها از ۰ و ۱ درست شده است.

حال فیشی تقلبی است که حداقل یکی از رشته‌های زیر، حداقل یک بار، در آن آمده باشد:

110,101,111,011 110, 101, 111, 011

برای فهم بیشتر به نمونه‌ها و توضیحشان مراجعه کنید.

دقت کنید که هر فیشی که تقلبی نباشد اصل است.

ورودی🔗

در تنها سطر ورودی nn آمده است که نمایانگر اندازه‌ی رشته‌ی فیش‌ها می‌باشد. 1n100 0001 \le n \le 100 \ 000

خروجی🔗

در تنها سطر خروجی باقیمانده‌ی تعداد فیش‌های اصل بر 109+710^9 + 7 را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4
Plain text

خروجی نمونه ۱🔗

6
Plain text

توضیح نمونه‌ی اول

فیش‌های زیر تقلبی اند: 0011,0101,0110,0111,1010,1011,1100,1101,1110,1111 0011, 0101, 0110, 0111, 1010, 1011, 1100, 1101, 1110, 1111 فیش‌های زیر اصل هستند: 0000,0001,0010,0100,1000,1001 0000, 0001, 0010, 0100, 1000, 1001

پس از کل ۱۶ حالت فیش‌ها، ۱۰ تا تقلبی و ۶ تا اصل هستند که چون سوال تعداد اصل‌ها را خواسته‌ است جواب برابر ۶ می‌شود.

ورودی نمونه ۲🔗

3
Plain text

خروجی نمونه ۲🔗

4
Plain text