Ще одна задача про тури#3439
У вас є тур та дошка m \times n. Розміщення тур на дошці називається правильним, якщо жодна тура не знаходиться між двома іншими турами горизонтально чи вертикально.
Для заданих , та знайдіть кількість правильних розміщень тур на дошці. Оскільки це число може бути достатньо великим, знайдіть його по модулю .
Вхідні дані містять , , і (1 \leq m, n \leq 50, 1 \leq k \leq m \cdot n).
Виведіть одне число — кількість правильних розміщень тур на дошці m \times n за модулем .
Приклад 1