Problem description

Podziałem liczby N na sumę K składników nazywamy przedstawienie liczby N w postaci niemalejącego ciągu (T₁,T₂,…,T_K), gdzie T_i to dodatnie liczby całkowite oraz T₁ + T₂ + … + T_K = 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 N_i – 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 N_i na dowolną liczbę składników przez 10⁹ + 7.

Ograniczenia

1 ≤ Q ≤ 1 000, 1 ≤ N_i ≤ 300 000.

W testach wartych łącznie 30% maksymalnej punktacji: N ≤ 2 000.

Przykład

2
4
3

5
3