== include(page="template/taskheader" task_id="preasimplu") ==

Arhitectul ierdnac s-a gandit la urmatoarea problema:

In drumul sau spre olimpiadele internationale Arhitectul Ierdnac s-a gandit la urmatoarea problema:

bq. Fie un sir binar b{~i~} cu $N$ elemente. Initial toti bitii sunt setati pe valoarea $0$. Fie $flip(l, r)$ o operatie ce schimba elementele sirului in felul urmator:
{*} Daca rangul elementului *nu* apartine intervalului $[l, r]$, atunci elementul respectiv ramane neschimbat;
{*} Altfel, elementul isi schimba valoarea (adica din $0$ devine $1$ si din $1$ devine $0$).

Se cere numarul de siruri finale ce se pot obtine daca se efectueaza fix $K$ operatii de $flip$ la alegere. Deoarece raspunsul poate fi foarte mare, se cere afisarea acestuia modulo $10^9^ + 7$.
 
Vazut fiind acolo, acesta s-a intalnit cu Bossu' Frumosu' si i-a povestit despre problema. Acesta a raspuns imediat prin faimoasa deja replica "Prea simplu!" si a sugerat

h2. Date de intrare