Wstęp do programowania w C++

Jasio właśnie przygotował swoje pierwsze bardzo skomplikowane zadanie algorytmiczne na konkurs "FRAKTAL". Bardzo się natrudził przy opracowaniu zestawów testowych.

Gdy już myślał, że zadanie jest gotowe i otworzył plik z danymi wejściowymi to zauważył, że popełnił straszliwy błąd. Otóż, przy generowaniu liczb reprezentujących dane wejściowe, zapomniał wstawić odstęp między liczbami. Jego test wyglądał jak ciąg nic nieznaczących cyfr.

Jasio chce odtworzyć ten ciąg rozpatrując wszystkie możliwe przypadki wstawienia odstępów pomiędzy cyframi. Na przykład, jeżeli wygenerowany test składa się z cyfr 123, to mógł on oznaczać następujące testy: 123 lub 1 23 lub 12 3 lub 1 2 3.

Napisz program, który uświadomi Jasiowi, że kombinacji jest zbyt wiele i że musi jeszcze raz stworzyć testy.

Wejście

W pierwszym wierszu jedna liczba n ∈ [1, 1000] określająca liczbę zestawów danych. W kolejnych n wierszach znajdują się zestawy danych.

Każdy zestaw danych zawiera jedną liczbę, z przedziału [1, 2×10⁹], określającą liczbę cyfr w teście Jasia. Jasio w swoim teście nie używał cyfry 0.

Wyjście

Dla każdego zestawu danych należy wypisać resztę z dzielenia liczby możliwych kombinacji przez 10⁹ + 7.

Przykład

2
3
1000000000

4
570312504