Две версии отличаются по ограничениям, включая ограничения на переменные, и также ограничения по времени и памяти. Вы можете взламывать только в том случае, если решите обе версии этой задачи. Обратите внимание, что корректное решение для сложной версии не обязательно является корректным решением для легкой версии.
У нас есть управляемая машина, которая ведет себя как случайная величина. Поскольку случайная величина не является поистине случайной и не является поистине переменной, наша управляемая машина не является ни машиной, ни управляемой!
Тем не менее, нам дано поле размером $$$n \times m$$$, образованное пересечением $$$n+1$$$ горизонтальных линий и $$$m+1$$$ вертикальных линий. Поле содержит $$$(n+1)(m+1)$$$ точек пересечения, которые являются углами, окружающими ячейки.
Ориентация — это назначение одного из четырех кардинальных направлений (вверх, вниз, влево, вправо) каждой из этих $$$(n+1)(m+1)$$$ точек пересечения. Следовательно, существует $$$4^{(n+1)(m+1)}$$$ возможных ориентаций.
Рассмотрим процесс ниже для ориентации:
- Для каждой точки на поле мы рисуем стену, пролегающую в направлении, в котором она ориентирована, длиной один. Стены могут перекрываться или выходить за границы поля.
- Поместите управляемую машину в верхнем левом углу: ячейке $$$(1, 1)$$$. Затем, пока машина не остановится, она движется в соответствии с этими правилами:
- Если она может двигаться вниз (т.е. никакая стена не блокирует путь к ячейке непосредственно ниже), она движется вниз из-за силы тяжести.
- Если она не может двигаться вниз, но может двигаться вправо (т.е. никакая стена не блокирует путь к ячейке непосредственно справа), она движется вправо.
- Если машина выходит за границы поля или не может двигаться, она останавливается.
- Ориентация считается корректной, если управляемая машина останавливается внутри поля.
Подсчитайте количество корректных ориентаций. Поскольку количество корректных ориентаций может быть огромным, выведите ответ по модулю $$$10^9+7$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 5000$$$), размеры поля.
Для каждого набора входных данных выведите количество корректных ориентаций по модулю $$$10^9+7$$$.
51 12 11 22 25000 5000
40107278491072793450807
В первом наборе входных данных, чтобы ориентация была корректной, нам нужно, чтобы хотя бы одна из стен нижнего левого или нижнего правого углов покрывала нижнюю границу квадрата. Нам также надо, чтобы хотя бы одна из стен верхнего правого или нижнего правого углов покрывала правую границу. Если оба этих условия выполняются, то ориентация корректна.
Теперь, если верхний правый угол направлен вниз, а нижний левый угол направлен вправо, то верхний левый и нижний правый углы могут указывать в произвольных направлениях. Следовательно, существует $$$16$$$ корректных ориентаций этого типа.
Пример корректной ориентации первого типа. Если один из верхнего правого или нижнего левого углов указывает в другом направлении, нижний правый угол должен покрывать соответствующую границу. Следовательно, только один из них может указывать в другом направлении. В общей сложности существует $$$2 \cdot 3 \cdot 4 = 24$$$ корректных ориентаций этого типа.
Пример корректной ориентации второго типа. Таким образом, окончательный ответ равен $$$16 + 24 = 40$$$.
Примеры двух некорректных ориентаций.
