İnək şahmatı (Gümüş)#11180
İnsanların şahmat oynamağı sevdiyi kimi, fermer Consun inəkləri də bu oyunun öz versiyasını uydurmuşlar. Bu oyunu az qala bir tonluq çəkiyə malik olan yöndəmsiz heyvanlar oynadığı üçün, "İnək şahmatı" demək olar ki, həmişə fəlakətlə nəticələnir. Lakin təəccüblüdür ki, bu, inəklərin demək olar ki, hər gün oynamasına mane olmur.
Oyun r \times c ölçülü sahədə keçirilir, burada hər bir xana diapazonundan olan bir tam ədədlə işarələnib. İnəklər yuxarı sol xanada başlayır və bir sıra düzgün tullanışlar edərək aşağı sağ xanaya çatmalıdırlar. Tullanış yalnız aşağıdakı şərtlər ödəndikdə düzgün sayılır:
Tullanılan xananın etiketi cari xananın etiketindən fərqlidir.
Tullanılan xana cari xanadan ən azı bir sətir aşağıdadır.
Tullanılan xana cari xanadan ən azı bir sütun sağdadır.
İnəklərə yuxarı sol xanadan aşağı sağ xanaya çatmalarına imkan verən müxtəlif düzgün tullanış ardıcıllıqlarının sayını tapmaqda kömək edin.
Birinci sətirdə üç tam ədəd — r, c~(2 \le r \le 100, 2 \le c \le 100) və k~(1 \le k \le r \times c) verilir. Növbəti sətirdə hər birində tam ədəd verilir, hər biri diapazonundadır.
Yuxarı sol xanadan aşağı sağ xanaya tullanışlar etməyin müxtəlif üsullarının sayını 10^9 + 7 moduluna görə çıxarın.
Nümunə 1