No.767 配られたジャパリまん
ミドリムシこちらの問題がヒントになるかもしれません。
問題文
あなたは今ジャパリパークという動物園のとある「ちほー」と呼ばれるエリアにいます。
このちほーは上下方向に $H$ メートル、左右方向に $W$ メートルの $(H+1)\times(W+1)$ の格子点から構成される升目で表現され、左上の格子点は $(0,0)$ 、右下の格子点は $(H,W)$ です。
このちほーにはフレンズと呼ばれるヒトの姿をした動物が $K$ 人おり、 $i$ 番目のフレンズは $(a_i, b_i)$ にいることがわかっています。また、一箇所にいるフレンズは高々 $1$ 人です。
フレンズのいる所は通ることができませんが、ジャパリまんというおまんじゅうを渡すと通れるようになります。
スタートやゴールにフレンズがいることはありません。
あなたは今 $(0,0)$ にいて、 $(H,W)$ まで右方向または下方向の移動のみで行こうとしています。
あなたは右方向または下方向の移動のみで $(H,W)$ まで行く経路 の個数 が気になっています。
様々なジャパリまんの渡し方について、右方向または下方向の移動のみで $(H,W)$ まで行く経路の個数を求めてください。
$2^K$ 個のクエリが与えられます。
$i$ 番目(1-indexed)のクエリにおいて、 $i-1$ の2進数表記の下から $j$ 番目(1-indexed)の桁が0ならそのクエリでは $j$ 番目のフレンズにジャパリまんを渡すことを、1ならそのクエリでは $j$ 番目のフレンズにはジャパリまんを渡さないことを表します。
各クエリについて、そのクエリが表すじゃぱりまんの渡し方をしたときの右方向または下方向の移動のみで $(H,W)$ まで行く経路の個数を $10^8+7$ で割った余りを出力してください。
$(H,W)$ まで行く経路がない場合は $0$ を出力してください。
入力
$H$ $W$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_K$ $b_K$
$H$ と $W$ はそれぞれこのちほーの上下方向と左右方向の長さを表しています。
$K$ はこのちほーにいるフレンズの数を表しています。
$a_i,b_i$ は $i$ 番目のフレンズが $(a_i,b_i)$ にいることを表しています。
$1≤H,W≤10^5$
$1≤K≤min(20, (H + 1) (W + 1) - 2)$
$0≤a_i≤H$
$0≤b_i≤W$
$i≠j$ のとき $(a_i, b_i)≠(a_j, b_j)$
ただし $a,b$ のどちらかのみが一致することはある
$(a_i, b_i) \ne (0,0),(H,W)$
（スタートとゴールにはフレンズはいない）
出力
$2^K$ 行出力し、 $i$ 行目には $i$ 番目のクエリの答えを出力してください。
出力が最大約100万行と多いので注意してください。
サンプル
サンプル1
入力
1 2 1 0 1
出力
3 1
$1$番目のフレンズにジャパリまんを渡す場合、経路は下右右、右下右、右右下の$3$通り。
$1$番目のフレンズにジャパリまんを渡さない場合、経路は下右右の$1$通り。
s-1-o | | | o-o-g
サンプル2
入力
3 3 2 2 1 1 2
出力
20 11 11 2
s-o-o-o | | | | o-o-2-o | | | | o-1-o-o | | | | o-o-o-g
サンプル3
入力
3 3 4 1 0 1 1 1 2 1 3
出力
20 10 8 4 11 4 5 1 16 7 6 2 10 3 4 0
s-o-o-o | | | | 1-2-3-4 | | | | o-o-o-o | | | | o-o-o-g
サンプル4
入力
20 18 5 4 9 18 2 3 10 18 8 17 10
出力
77998265 17271238 77969195 17242168 68667836 7940809 68638766 7911739 74888122 14161095 74871592 14144565 65557693 4830666 65541163 4814136 86011338 26935961 85982268 26906891 76728099 17652722 76699029 17623652 82901195 23825818 82884665 23809288 73617956 14542579 73601426 14526049
$10^8+7$で割るのを忘れずに。
サンプル5
入力
3000 3000 10 685 339 1255 1743 1838 961 668 2662 2688 1546 1675 1056 2953 2056 196 460 1990 955 243 2303
出力
41851678 88930621 75240276 13062597 90869769 72043296 24258360 96175279 79892182 26971118 13280773 51103101 ... (長いので省略) 33023592 38873219 93287621 95644688 78014337 89484964 66543267 63279334 51269983 57119610
サンプル6
入力
70000 90000 16 65133 3336 12082 88737 57559 1709 2660 8526 30136 27968 34819 40321 8688 26480 6491 65230 37371 69584 1876 13309 63014 1937 69427 8281 1355 77227 57115 1528 935 14747 61758 57582
出力
15709191 85308639 86356296 55955737 24627065 24785722 95274170 95432827 13298101 82897549 57412092 27011533 22215975 22374632 ... (長いので省略)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。