AlgoLiga 2018

W pewnej bajtlandzkiej fabryce czekolady organizer Balteusz zajmował się produkcją kwadratowych tabliczek czekolad, które później pakował do sześciennych opakowań. Maszyny do produkcji czekolad działały następująco:

Balteusz ustawiał rozmiar najmniejszej tabliczki czekolady i największej (jednostką tejże czekolady jest oczywiście jedna kostka). Maszyna produkowała zawsze tylko tyle czekolady o danym wymiarze, aby zapełnić tylko jeden sześcienny karton, następnie zwiększała wymiar tabliczki o jedną kostkę i czynność powtarzała, aż zostały wyprodukowane wszystkie wymiary i w taki sposób aby otrzymać dokładnie jeden karton każdego rozmiaru.

Na przykład, jeśli najmniejszy rozmiar to 3, a największy to 5, maszyna wyprodukowała 3 tabliczki czekolady o wymiarach 3 x 3, 4 tabliczki 4 x 4 oraz 5 tabliczek 5 x 5. Balteusz znał średnią liczbę kostek czekolady, jaką zjadali bajtlandczycy, więc musiał także wiedzieć ile mniej więcej kostek musi wyprodukować. W pewnym momencie ta liczba stała się bardzo duża, a obliczenia zbyt czasochłonne. Poproszono więc znanego programistę (ciebie), żeby napisał w tym celu program wyliczający liczbę wyprodukowanych kostek czekolady.

Wejście

Pewna liczba zestawów danych (nie więcej niż 10⁵). Każdy zestaw składa się z dwóch liczb a ≤ b oraz a, b ∈ [1... 10⁹], określających najmniejszy i największy rozmiar tabliczki czekolady.

Wyjście

Dla każdego zestawu liczba wyprodukowanych kostek czekolady modulo 1010101011.

Przykład

Wejście:
2 5
8 12
9 9

Wyjście:
224
5300
729