Вам заданы два числа \(n\) и \(m\). Посчитайте количество таких пар массивов \((a, b)\), что:
- длина обоих массивов равна \(m\);
- каждый элемент каждого массива — целое число от \(1\) до \(n\) (включительно);
- \(a_i \le b_i\) для любого индекса \(i\) от \(1\) до \(m\);
- массив \(a\) отсортирован в порядке неубывания;
- массив \(b\) отсортирован в порядке невозрастания.
Так как ответ может быть слишком большим, посчитайте его по модулю \(10^9+7\).
Выходные данные
Выведите одно число – количество массивов \(a\) и \(b\), удовлетворяющих условиям, описанным выше по модулю \(10^9+7\).
Примечание
В первом тесте существуют \(5\) подходящих вариантов:
- \(a = [1, 1], b = [2, 2]\);
- \(a = [1, 2], b = [2, 2]\);
- \(a = [2, 2], b = [2, 2]\);
- \(a = [1, 1], b = [2, 1]\);
- \(a = [1, 1], b = [1, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
|
5
|
|
2
|
10 1
|
55
|
|
3
|
723 9
|
157557417
|