No.584 赤、緑、青の色塗り

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

問題文

$1$行$N$列のまだ色が塗られていないマスがある。
以下のルールで色塗りを行う。

・赤、緑、青の色でそれぞれ指定された数だけマスを塗る。
・空白のマスが残っても良い。空白のマスは色が塗ってあるマスとはみなさない。
・同じ色は各列隣り合った両方のマスに塗ることはできない。
・異なる色であれば連続して$2$つのマスまで隣り合って色を塗っても良い。
・連続して$3$つ以上のマスに色を塗ることはできない。

以上のルールで色を塗る方法は何通りか?
$1000000007$で割った余りを答えよ。

入力

$N$ $R$ $G$ $B$

$N$、$R$、$G$、$B$は整数。$1\le N \le 3000$。$0\le R,G,B \le 3000$。
$N$はマスの列数。$R$、$G$、$B$はそれぞれ赤、緑、青で塗るべきマスの数。

出力

答えを1行で出力せよ。
答えとなる塗り方が存在しない場合は0通りを答えとする。
最後に改行を忘れずに。

サンプル

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

左から
「赤、青、空白、赤、青」
「赤、青、空白、青、赤」
「青、赤、空白、赤、青」
「青、赤、空白、青、赤」
以上の4通りで色を塗ることができます。

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

左から「赤、空白、赤」の1通りしかありません。

サンプル3
入力
7 0 1 0
出力
7

7つのマスのいずれか1つを緑で塗ります。答えは7通りです。

サンプル4
入力
3 1 1 1
出力
0

赤、緑、青で$1$つずつ色を塗らなければなりません。
しかし、連続して$3$つ以上のマスに色を塗ることはできません。
塗る方法がないので答えは$0$通りです。

サンプル5
入力
6 2 1 1
出力
54

サンプル6
入力
300 10 20 0
出力
470935914

答えは1000000007で割った余りになるので注意してください。

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

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