Codeforces Round #274 (Div. 2) E. リフトに乗る（DP）_html/css_WEB-ITnose

あなたがちょうど n 階ある建物にいると想像してください。フロア間はエレベーターで移動できます。 1 から n までの整数を使用して、下から上にフロアに番号を付けましょう。今、あなたはフロア番号 a にいます。あなたはとても退屈しているので、エレベーターに乗りたいと思っています。階番号 b には秘密の研究室があり、立ち入りは禁止されています。しかし、あなたはすでに気分が高揚しており、エレベーターに k 回連続して乗ることにしました。

現在、フロア番号 x にいると仮定します（最初はフロア a にいました）。フロア間の別の移動では、番号 y (y?≠?x) のフロアを選択すると、エレベーターがこのフロアまで移動します。シークレット ラボではフロア b にアクセスできないため、現在のフロア x から選択したフロア y までの距離は、現在のフロア x からシークレット ラボのあるフロア b までの距離よりも厳密に小さくなければならないと判断しました。形式的には、次の不等式が満たされる必要があることを意味します: |x?-?y|?|x?-?b|。エレベーターが y 階に正常に移動したら、数字 y をメモ帳に書き留めます。

あなたの課題は、エレベーターで k 回移動した結果としてノートに書き込むことができる個別の数字列の数を見つけることです。求められる乗車数はかなり大きくなる可能性があるため、数値を 1000000007 (109?+?7) で割った余りを求めます。

入力

入力の最初の行には、スペースで区切られた 4 つの整数 n、a が含まれます。 , b, k (2?≤?n?≤?5000, 1?≤?k?≤?5000, 1?≤?a,?b?≤?n, a?≠?b)。

出力

単一の整数を出力しますか?求めたシーケンス数を 1000000007 (109?+?7) で割った余り。

サンプル テスト

入力

5 2 4 1

出力

入力

出力

出力

入力

5 2 4 2

出力

题意：做電梯、刚始始的候你在a层、不可能b层、次回訪問的y、must须满足|x-y |<|x-b|、求坐k次有量可能性

思路: 比较容易に想起される是dp[i][j] 表示最初に了j層の可能性、分情况论、例: 当a< b の天気では、次の層数 i は j+(b-j-1)/2 を超えることができず、その後毎回事前に処理されて前の j 層が削除される可能性があります。