prithivMLmods/Coder-Stat

1<h1>座席 (Seats)　</h1>2<!--　　時間制限 : 5sec / メモリ制限 : 256MB -->3 4<h2> 問題文</h2>5 6<p>72XXX 年，世界の国は直線状に並んでいた．<var>N</var> 個の国があり，<var>1, 2, ..., N</var> の番号が付けられている．<var>i = 1, 2, ..., N - 1</var> に対し，国 <var>i</var> と国 <var>i + 1</var> が互いに隣国である．8</p>9 10<p>11この年の国際情報オリンピックでは，国 <var>i</var> からは <var>A_i</var> 人の選手が参加する．国際情報オリンピックの技術委員のあなたは，競技での座席表を作成する担当である．競技会場が細長いため，一列に並んだ <var>A_1 + A_2 + ... + A_N</var> 個の座席に選手たちを割り当てることになった．不正防止のため，同じ国の選手や隣国の選手を隣り合う席に割り当ててはならない．12</p>13 14<p>15選手たちを座席に割り当てる方法は何通りあるだろうか．この数は非常に大きくなる可能性があるので，それを <var>10007</var> で割った余りを求めたい．16</p>17 18<h2>制約</h2>19 20<ul>21<li><var>1 ≦ N ≦ 100</var></li>22<li><var>1 ≦ A_i ≦ 4</var> (<var>1 ≦ i ≦ N</var>)</li>23</ul>24 25<h2> 入力・出力</h2>26 27<p>28<b>入力</b><br>29入力は以下の形式で標準入力から与えられる．<br>30<var>N</var><br>31<var>A_1</var> <var>A_2</var> <var>...</var> <var>A_N</var>32</p>33 34<p>35<b>出力</b><br>36選手たちを座席に割り当てる方法の数を <var>10007</var> で割った余りを <var>1</var> 行で出力せよ．37</p>38 39<!--40<h2>小課題</h2>41<p style="line-height: 200%;  margin-left: 30px; margin-right: 30px;">42</p>43 44<p style="line-height: 200%;  margin-left: 30px; margin-right: 30px;">45<ol style="line-height: 200%;  margin-left: 30px; margin-right: 30px;">46<li>(<var>6</var> 点) <var>N ≦ 5</var>，<var>A_i ≦ 2</var> (<var>1 ≦ i ≦ N</var>)</li>47<li>(<var>14</var> 点) <var>N ≦ 10</var>，<var>A_i ≦ 3</var> (<var>1 ≦ i ≦ N</var>)</li>48<li>(<var>80</var> 点) 追加の制約はない．</li>49</ol>50</p>51-->52 53<h2>入出力例</h2>54 55<h3>入力例 1</h3>56<pre>574582 1 1 159</pre>60 61<h3>出力例 1</h3>62<pre>63464</pre>65 66<p>67国 <var>1</var> から参加する <var>2</var> 人の選手を <var>1</var> と <var>1'</var>，国 <var>2</var> から参加する <var>1</var> 人の選手を <var>2</var>，国 <var>3</var> から参加する <var>1</var> 人の選手を <var>3</var>，国 <var>4</var> から参加する <var>1</var> 人の選手を <var>4</var> で表すことにすると，選手たちを座席に割り当てる方法としては，以下の <var>4</var> 通りの並べ方が考えられる：68</p>69 70<ul>71<li><var>1</var>, <var>3</var>, <var>1'</var>, <var>4</var>, <var>2</var></li>72<li><var>1'</var>, <var>3</var>, <var>1</var>, <var>4</var>, <var>2</var></li>73<li><var>2</var>, <var>4</var>, <var>1</var>, <var>3</var>, <var>1'</var></li>74<li><var>2</var>, <var>4</var>, <var>1'</var>, <var>3</var>, <var>1</var></li>75</ul>76 77<h3>入力例 2</h3>78<pre>795801 2 3 2 181</pre>82 83<h3>出力例 2</h3>84<pre>85086</pre>87 88<p>89この入力例では，条件を満たす座席表は存在しない．90</p>91 92<h3>入力例 3</h3>93<pre>946951 2 3 3 2 196</pre>97 98<h3>出力例 2</h3>99<pre>1004754101</pre>102 103<p>104この入力例では，選手たちを座席に割り当てる方法は <var>24768</var> 通りあるため，それを <var>10007</var> で割った余りである <var>4754</var> を出力する．105</p>106 107<br/>108<div class="source">109<p class="source">110<a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/80x15.png"/></a>111</p>112<p class="source">113<a href="https://www.ioi-jp.org/joi/2018/2019-yo/index.html">情報オリンピック日本委員会作 『第 18 回日本情報オリンピック JOI 2018/2019 予選競技課題』</a>114</p>115</div>116