Последовательность пар целых чисел (a1, b1), (a2, b2), ..., (ak, bk) называется красивой, если выполнены два условия:
- 1 ≤ a1 ≤ b1 < a2 ≤ b2 < ... < ak ≤ bk ≤ n, где n — заданное целое положительное число;
- все числа b1 - a1, b2 - a2, ..., bk - ak различные.
Для заданного числа n найдите количество красивых последовательностей длины k. Так как ответ может быть достаточно большим, выведите его остаток от деления на 1000000007 (109 + 7).
Выходные данные
Для каждого теста из входных данных выведите ответ на задачу по модулю 1000000007 (109 + 7). Ответы для тестов выводите в том порядке, в котором тесты заданы во входных данных.
Примечание
В первом тестовом примере ровно одна красивая последовательность: (1, 1).
В втором тестовом примере следующие последовательности являются красивыми:
В четвертом тестовом примере следующие последовательности являются красивыми:
- (1, 1);
- (1, 2);
- (1, 3);
- (2, 2);
- (2, 3);
- (3, 3).
В пятом тестовом примере следующие последовательности являются красивыми:
- (1, 1), (2, 3);
- (1, 2), (3, 3).
В третьем и шестом тестовых примерах красивых последовательностей нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1
2 1
2 2
3 1
3 2
3 3
|
1
3
0
6
2
0
|