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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 32
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : tubo28tubo28
3 ProblemId : 1883 / 出題時の順位表
問題文最終更新日: 2017-10-28 00:21:31

問題文

$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で割った余りになるので注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。