Вам дана шахматная доска размером \(n \times n\), на которой вы и компьютер поочередно расставляете белые и черные ладьи соответственно. Расставляя ладьи, вы должны следить за тем, чтобы никакие две ладьи не атаковали друг друга. Две ладьи атакуют друг друга, если они находятся в одной строке или столбце независимо от цвета.
Правильный ход — установка ладьи на позиции (\(r\), \(c\)) так, чтобы она не атаковала никакую другую ладью.
Вы начинаете первым, и когда вы в свой ход сделаете правильный ход, поставив белую ладью на позицию (\(r\), \(c\)), компьютер отзеркалит ваш ход и в свой ход поставит черную ладью на позицию (\(c\), \(r\)). Если \(r = c\), то компьютер не сможет отзеркалить ваш ход и пропустит его.
Вы уже сыграли с компьютером \(k\) ходов (компьютер отразил и эти ходы), и вы должны продолжать игру, пока не останется ни одного правильного хода. Сколько различных конечных конфигураций можно получить, если продолжить игру после данных \(k\) ходов? Гарантируется, что \(k\) сделанных ходов были правильными. Так как ответ может быть большим, выведите его по модулю \(10^9+7\).
Две конфигурации считаются различными, если существует координата (\(r\), \(c\)), в которой ладья есть в одной конфигурации, но нет в другой, или цвет ладьи на координате отличается.
Примечание
В первом наборе входных данных у нас есть поле \(4 \times 4\), и вы уже сыграли \(1\) ход. После того как вы и компьютер сыграли по одному ходу, на поле есть белая ладья на (\(1\), \(2\)) и черная ладья на (\(2\), \(1\)). Из этого состояния возможны три конфигурации —
- Вы ставите белую ладью на (\(3\), \(4\)), а компьютер в ответ ставит черную ладью на (\(4\), \(3\)).
- Вы ставите белую ладью на (\(4\), \(3\)), а компьютер в ответ ставит черную ладью на (\(3\), \(4\)).
- Вы ставите белую ладью на (\(3\), \(3\)), а затем на (\(4\), \(4\)), или наоборот. Оба варианта приводят к одной и той же конфигурации.
