Problem 98: Iftode

Zgăbeață Iftode este fiul unui cârciumar din Văscăuți. Drept pedeapsă pentru proasta impresie lăsată în timpul inspecției domnului director, domnul pedagog a ordonat întregii clase să rezolve un exercițiu greu de matematică.

Pedagogul și elevul Zgăbeață Iftode. Dem Rădulescu și Vasile Muraru în “Doi Vulpoi” (1983).

Asupra unui număr natural X se pot efectua următoarele trei tipuri de operații:

Adună 1 la X. Astfel, noua valoare a lui X va fi X + 1.
Scade 1 din X. Astfel, noua valoare a lui X va fi X − 1. Operația este validă doar pentru X > 0.
Înjumătățește X. Astfel, noua valoare a lui X va fi $\frac{X}{2}$ . Operația este validă doar pentru X par.

Oricare ar fi numărul inițial X este întotdeuna posibil ca prin operații de tipul celor de mai sus să se ajungă în cele din urmă la X = 0. Să notăm numărul minim de operații necesare cu $c_{X}$ . De exemplu, $c_1 = 1$ , deoarece putem efectua o operație de tipul 2 și să ajungem la 0, $c_7 = 5$ , deoarece putem efectua operațiile astfel: 7 → 8 → 4 → 2 → 1 → 0, iar $c_6 = 4$ , deoarece putem proceda astfel: 6 → 3 → 2 → 1 → 0.

Iftode a găsit într-o veche carte de matematică o metodă eficientă de calcul a lui $c_X$ , după cum urmează (se garantează că această metoda este corectă):

c_X = \left\{ \begin{array}{ll} 0 & X = 0 \\ 1 + c_{\frac{x}{2}} & X > 0 \text{ și par} \\ 3 & X = 3 \\ 1 + c_{X+1} & X ≠ 3, \text{impar și } \frac{X-1}{2} \text{ impar} \\ 1 + c_{X-1} & \text{ altfel} \end{array} \right.

Pedagogul le cere elevilor să calculeze suma $S = \sum_{X=L+1}^{R} c_X$ pentru două numere L, R date. Răspunsul se vrea modulo 1 000 000 007. Mai rău, numerele L, R vă sunt puse la dispoziție in baza 2.

Date de intrare

Pe prima linie se găsește numărul L. Pe a doua linie se găsește numărul R. Numerele se dau în baza 2.

Date de ieșire

Se va afișa pe primul rând suma S, modulo 1 000 000 007.

Restricții

Subtask 1 (2 puncte)

$0 ≤ L ≤ R < 2^{18}$

Stubatsk 2 (7 puncte)

$0 ≤ L ≤ R < 2^{60}$

Subtask 3 (5 puncte)

$0 ≤ L ≤ R < 2^{300}$
$R - L ≤ 10^5$

Subtask 4 (7 puncte)

$0 ≤ L ≤ R < 2^{300}$

Subtask 5 (7 puncte)

$0 ≤ L ≤ R < 2^{800}$

Subtask 6 (8 puncte)

$0 = L ≤ R < 2^{2 \ 500}$
R + 1 este putere de 2

Subtask 7 (7 puncte)

$0 ≤ L ≤ R < 2^{2 \ 500}$

Subtask 8 (9 puncte)

$0 = L ≤ R < 2^{100 \ 000}$
R + 1 este putere de 2

Subtask 9 (48 puncte)

$0 ≤ L ≤ R < 2^{100 \ 000}$

Exemple

stdin

100
111

stdout