Рабочие установили окно размером W дециметров в ширину и H дециметров в высоту. Но они забыли, что оно должно состоять из секций. Как известно, прямоугольные секции у любого окна образуют сетку, при этом соседние слева и справа по стороне секции одинаковы. Также известно, что длина и ширина каждой секции должны быть целым ненулевым количеством дециметров, а также что количество секций по вертикали и по горизонтали должно быть больше одной. Ниже приведены два примера разбиения окна 4 × 3 на секции:
Чтобы не ставить новое окно с секциями, рабочие решили наклеить на него горизонтальные и вертикальные перегородки от одного края до противоположного так, чтобы окно казалось поделенным на секции. Найдите количество способов это сделать.
Исходные данные
В первой строке даётся целое число W — ширина окна (2 ≤ W ≤ 106).
Во второй строке даётся целое число H — высота окна (2 ≤ H ≤ 106).
Результат
Выведите количество способов наклеить на окно горизонтальные и вертикальные перегородки так, чтобы оно казалось поделенным на секции. Поскольку это число может быть большим, выведите остаток от деления этого числа на 109 + 7.
Пример
| исходные данные | результат |
|---|
4
3
| 6
|
Автор задачи: Вадим Баринов
Источник задачи: Квалификационный тур Уральского регионального чемпионата ICPC 2026: отбор УрФУ