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:

1. Adună 1 la X. Astfel, noua valoare a lui X va fi X + 1.
2. Scade 1 din X. Astfel, noua valoare a lui X va fi X − 1. Operația este validă doar pentru X > 0.
3. Î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ă):

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

13

stdin

10110111110101
110000101010110

stdout

256512

Explicații

În primul exemplu L = 4 și R = 7. Avem că $c_5 = 4, c_6 = 4, c_7 = 5$, a căror sumă este S = 13.

În al doilea exemplu L = 11765 și R = 24918. Suma cerută este $S = \sum_{X=11766}^{24918} c_X = 256512$.