Для заданных целых чисел \(n\) и \(m\) назовем пару массивов \(a\) и \(b\) целых чисел хорошей, если они удовлетворяют следующим условиям:
- \(a\) и \(b\) имеют одинаковую длину, пусть их длина равна \(k\).
- \(k \ge 2\) и \(a_1 = 0, a_k = n, b_1 = 0, b_k = m\).
- Для каждого \(1 < i \le k\) имеет место следующее: \(a_i \geq a_{i - 1}\), \(b_i \geq b_{i - 1}\), и \(a_i + b_i \neq a_{i - 1} + b_{i - 1}\).
Найдите сумму \(|a|\) по всем хорошим парам массивов \((a,b)\). Поскольку ответ может быть очень большим, выведите его по модулю \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — сумму \(|a|\) по всем хорошим парам массивов \((a,b)\) по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных, хорошими парами массивов являются
- \(([0, 1], [0, 1])\), длина = \(2\).
- \(([0, 1, 1], [0, 0, 1])\), длина = \(3\).
- \(([0, 0, 1], [0, 1, 1])\), длина = \(3\).
Следовательно, сумма длин будет \({2 + 3 + 3} = 8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1
1 2
2 2
100 100
|
8
26
101
886336572
|