No.802 だいたい等差数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 49
作問者 : tempura_pptempura_pp / テスター : heno_codeheno_code
10 ProblemId : 2778 / 出題時の順位表

問題文

長さ$N$の整数列$A_1,A_2,...,A_N$であって、 以下の条件をすべてみたすものの個数を$10^9+7$で割った余りを求めてください。

  • $1 \le A_1 \le A_2 \le \ ...\ \le A_N \le M$
  • $1\le i \le N-1$なるすべての整数$i$に対して、$D_1 \le A_{i+1}-A_i \le D_2$
ただし、数列$A'$と$A''$が異なるとは、ある$i$が存在して$A'_i\ne A''_i$であることをいいます。

入力

$N\ M\ D_1\ D_2$

  • $2\le N \le 3×10^5$
  • $1\le M\le 10^6$
  • $0\le D_1\le D_2\le M$
  • 入力はすべて整数

出力

条件をみたす整数列の個数を$10^9+7$で割った余りを1行に出力してください。

サンプル

サンプル1
入力
3 5 1 2
出力
8

条件をみたす数列は以下の8つです。
$(1,2,3), (1,2,4), (1,3,4), (1,3,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5)$

サンプル2
入力
3 5 2 2
出力
1

サンプル3
入力
5 2 1 1
出力
0

サンプル4
入力
3141 592653 58 97
出力
200759484

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。