Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_16_11 - Odstępy

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×109], 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 109 + 7.

Przykład

Wejście:
2
3
1000000000
Wyjście:
4
570312504

Dodane przez:Marcin Kasprowicz
Data dodania:2022-12-16
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.