Problem description
Podziałem liczby N na sumę K składników nazywamy przedstawienie liczby N w postaci niemalejącego ciągu (T1,T2,…,TK), gdzie Ti to dodatnie liczby całkowite oraz T1 + T2 + … + TK = N.
Przykładowo, oto wszystkie podziały liczby 4: 4, 1 + 3, 2 + 2, 1 + 1 + 2, 1 + 1 + 1 + 1.
Napisz program, który: wczyta liczby naturalne N, wyznaczy dla każdej z nich liczbę podziałów na dowolną liczbę składników i wypisze wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q – liczba zestawów danych. W kolejnych Q wierszach znajduje się opis kolejnych zestawów danych, po jednym w wierszu. Opis każdego zestawu danych składa się z jednej liczby naturalnej Ni – liczby dla której należy wyznaczyć liczbę podziałów.
Wyjście
Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź dla każdego zestawu danych składa się z jednej liczby całkowitej – reszty z dzielenia liczby podziałów liczby Ni na dowolną liczbę składników przez 109 + 7.
Ograniczenia
1 ≤ Q ≤ 1 000, 1 ≤ Ni ≤ 300 000.
W testach wartych łącznie 30% maksymalnej punktacji: N ≤ 2 000.
Przykład
| Input | Output | |
|
|