Жил-поживал на не совсем обычной шахматной доске не совсем обычный слон. Доска была не совсем обычной, так как была произвольного размера N × M. Слон был не совсем обычным, потому что стоял на угловой клетке. Стоял он, стоял, и заскучал. И решил отправиться в путешествие куда глаза глядят. А глаза у слонов, как известно, глядят по диагонали. Достигнув края доски, слон поворачивал на 90 градусов и продолжал движение. Остановился он только тогда, когда опять попал в какой-то (первый попавшийся) из углов.
Сколько всего уникальных полей слон обошел за свое путешествие по доске N × M ?
В первой и единственной строке находятся целые числа N и M — размеры шахматной доски.
В единственной строке выведите одно число — количество пройденных слоном клеток по простому модулю 1018 + 9.
15 22
42
