在代達羅斯建造的迷宮中,有個區域是被下了神秘魔法的方陣,高為 N,寬為 M,入口在左上角,而出口是個會隨日期變化的傳送門,以 Q 天為一個變化週期。因為此地的魔法規則,每次移動只能往右或往下移動一格。方陣中有些地方會有石柱,它們會擋住去路。伊卡洛斯今天很無聊,想請你計算在各個日期中,從入口走到出口的方式有幾種。
第一行有三個數字 N,M,Q,代表方陣的高、寬、出口變化的週期。 接下來 N 行,每行有 M 個屬於 0,1 的數字,1 代表這個位置有石柱,反之則無。入口一定沒有石柱。 再接下來 Q 行,每行有 2 個數字 xi,yi,代表第 i 天的出口座標,xi 是縱座標,由上往下遞增;yi 是橫座標,由左往右遞增。
Q 行,每行輸出當天走到出口的方法數除以 109+7 的餘數。