Последний присоединившийся последователь Омкара, Ajit, вошел в Священный лес. Ajit понимает, что лес Омкара — это таблица размером \(n\) на \(m\) (\(1 \leq n, m \leq 2000\)), состоящая из целых неотрицательных чисел. Поскольку лес благословлен Омкаром, он удовлетворяет некоторым особым условиям:
- Для любых двух соседних по стороне клеток абсолютное значение разности чисел в них не превышает \(1\).
- Если число в какой-то клетке строго больше \(0\), то оно должно быть строго больше, чем значение числа в по крайней мере одной клетке, примыкающей к ней по стороне.
К сожалению, Ajit еще не полностью достоин способностей Омкара. Он видит каждую клетку как "0" или "#". Если клетка обозначена как "0", то число в ней должно быть равно \(0\). Иначе число в ней может быть любым неотрицательным целым числом.
Определите, сколько существует различных конфигураций элементов, при которых выполняются эти особые условия. Две конфигурации считаются различными, если существует хотя бы одна клетка такая, что числа, записанные в ней в этих конфигурациях, различны. Поскольку ответ может быть огромным, найдите ответ по модулю \(10^9+7\).