Коров'ячі класики (Срібло)#11180
Так само, як людям подобається грати у класики, корови фермера Джона придумали власну версію цієї гри. Оскільки в неї грають незграбні тварини вагою майже в тонну, «Коров'ячі класики» майже завжди закінчуються катастрофою. Однак, що дивно, це не заважає коровам грати майже щодня.
Гра відбувається на полі розміром r \times c, де кожна клітинка позначена цілим числом з діапазону . Корови починають у верхній лівій клітинці і повинні дістатися до нижньої правої клітинки, виконуючи послідовність стрибків. Стрибок є допустимим тоді і тільки тоді, коли виконуються наступні умови:
Клітинка, у яку виконується стрибок, має метку, відмінну від метки поточної клітинки.
Клітинка, у яку виконується стрибок, знаходиться щонайменше на один рядок нижче поточної клітинки.
Клітинка, у яку виконується стрибок, знаходиться щонайменше на один стовпець правіше поточної клітинки.
Допоможіть коровам визначити кількість різних послідовностей допустимих стрибків, які дозволяють їм дістатися з верхньої лівої клітинки до нижньої правої.
У першому рядку містяться три цілих числа r, c~(2 \le r \le 100, 2 \le c \le 100) і k~(1 \le k \le r \times c). У наступних рядках міститься по цілих чисел, кожне з яких знаходиться в діапазоні .
Виведіть кількість різних способів виконати стрибки з верхньої лівої клітинки до нижньої правої за модулем 10^9 + 7.
Приклад 1