joisc2009 誘拐(Abduction)（難易度8）
実装が面倒くさそうに見えるけど実際にやってみると意外に簡単な例
解説
こういう問題は縦と横に分離して考えるのが定石（らしい）。
1回目にどっちに曲がったかで縦に出発したか横に出発したかが分かって、その後の曲がった順番から上下左右の4方向のどこに進んだかが特定できる。
ここで、縦と横に分離して考える。縦と横でそれぞれ行き方が何通りあるかが分かれば、後はそれらをかけ合わせたものが答えになる。
なので例えば縦に注目すると、dp[i][j] = i回目に縦に進んでj列に到達する場合の数と置くと、dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]という漸化式が成り立つ。
横も同様にすればいい。
注意点
dp配列は使い回さないとMLEする（昔のJOIの悪いところ）
modが10^7なので変え忘れない