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$).

bq. Fie un sir binar b{~i~} cu $N$ elemente. Initial toti bitii sai sunt setati pe valoarea $0$. Fie $flip(l, r)$ o operatie ce schimba elementele sirului in felul urmator:
{*} Daca rangul elementului la care ne referim *nu* apartine intervalului $[l, r]$, atunci elementul respectiv ramane neschimbat;
{*} Altfel, elementul isi schimba valoarea (adica din $0$ devine $1$ si, respectiv, 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 destul de 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 mai multe metode de a complica artificial problema. Dupa lungi deliberari, comisia a decis - numarul de solutii va trebui afisat modulo un numar natural nenul $MOD$ arbitrar!