Свинка Пеппа во время прогулки попала в лес. По странному совпадению лес имеет форму прямоугольника, состоящего из n строк и m столбцов. Занумеруем строки прямоугольника сверху вниз числами от 1 до n, а столбцы — слева направо числами от 1 до m. Будем обозначать клетку на пересечении r-й строки и c-го столбца как (r, c).

Исходно свинка стоит в клетке (1, 1), а в конце она хочет оказаться в клетке (n, m). Так как свинка торопится домой, из клетки (r, c) она может перейти только в клетку (r + 1, c) либо (r, c + 1), при этом выходить за пределы леса она не может.

Лес, в котором оказалась свинка, очень необычный. Некоторые клетки леса похожи между собой, а некоторые выглядят совершенно по-разному. Пеппа любит фотографировать и на каждом шагу делает фотографию клетки, в которой она сейчас находится. Путь по лесу считается красивым, если фотографии, полученные на её пути, можно рассматривать как в прямом, так и в обратном порядке, будет получаться одна и та же последовательность фотографий. Более формально, строка, образованная клетками в порядке посещения, должна являться палиндромом (формальное определение палиндрома можете прочитать в условии предыдущей задачи).

Посчитайте количество красивых путей из клетки (1, 1) в клетку (n, m). Так как это число может быть очень большим, определите остаток от деления его на 10⁹ + 7.