排組雞
發布時間: July 6, 2024, 1:07 a.m. 最後更新時間: July 16, 2024, 2:50 p.m. 時間限制: 1000ms 記憶體限制: 128M
排...組...機...?
¯\_ಠ_ಠ_/¯
在一個月黑風高的正午，hush正眉頭深鎖，仔細思考這三個字的意思。
「排組機是什麼？」他自言自語的說。
「是排組還是雞呢？」「那為什麼不是排組鴨？」
正當他不知所措時，忽然有一個聲音告訴他：「排組機就是排列組合機率嘛！」
＼(◎o◎)／「OMG！原來就是這麼一回事啊！我以前從沒想過中文還有這種排列組合呢！」他像個寫了AC code似的手舞足蹈著。
「既然這樣，那我要出一個排組雞的題目挑戰你！」hush對著那個不知從何處來的聲音發起了挑戰。第四次數學危機一觸即發！
「接招吧！」
「雞，為了練出讓人垂涎欲滴的雞腿每天都在訓練場裡面水平或垂直狂奔(從左上角到右下角)。但是，雞不可濕，有些路上面有水，這是它無法接受的！然後"桃園機捷"四個字告訴我們雞只走捷徑。而且眾所皆知雞會飛，不過無法飛很遠也不能飛越過水上，因為輕功太難了。給你訓練場的地圖以及雞的飛行能力，你能夠算出它總共有幾種路徑可以訓練嗎？」hush一口氣把題目說完。
「偷偷告訴你，由於答案可能很大，請對把答案對$10^9+7$取餘數。」
第一行給你三個正整數$n, m, k$，代表訓練場有$n$行$m$列以及雞一次最多可以飛k格($3\le n,m\le 300$, $1\le k\le 30$)
_c___ -> ___c_ 從第$1$格到第$3$格是飛$2$格
接下來有$n$行，每行有$m$個字元，'#'代表水，'_'代表路
保證最外圍都是水
範例:
5 6 1
######
#____#
##___#
#_#__#
######
輸出一個整數代表從$(1,1)$走到$(n-2,m-2)$有幾種方法
範例輸出: 5
###### ###### ###### ###### ######
#→→→↓# #→→↓_# #→→↓_# #→↓__# #→↓__#
##__↓# ##_→↓# ##_↓_# ##→→↓# ##→↓_#
#_#_1# #_#_2# #_#→3# #_#_4# #_#→5#
###### ###### ###### ###### ######
5 6 1 ###### #____# ##___# #_#__# ######
5
5 6 2 ###### #____# #____# #____# ######
32
