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