시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB933100.000%

문제

길이가 $L$인 원형 정수열 $[h_1, h_2, \cdots , h_L]$이 있다고 하자. $h_i$와 $h_{i+1}$는 인접해 있으며, 특별히 $h_L$과 $h_1$이 인접해 있는 형태다. 이 원형 정수열의 점수는 같은 수들이 인접한 부분의 크기를 모두 구해서 곱한 것이다. 예를 들어 $h = [1, 1, 2, 2, 1, 3, 3, 3, 1, 1]$ 이면, 점수는 $4 \times 2 \times 1 \times 3 = 24$점이 된다.

$1$이상 $N$이하의 정수만 포함하면서, 정수 $a$를 정확히 $C_a$개 포함하는 서로 다른 원형 정수열에 대해서 점수의 총합을 구하는 프로그램을 작성하라. 두 원형 정수열 $h$와 $h'$이 다르다는 것은 $h_i \ne h'_i$인 $i$가 존재한다는 것이다.

입력

첫 번째 줄에 하나의 정수 $N$($1 ≤ N ≤ 50$)이 주어진다.

두 번째 줄에는 $N$개의 정수 $C_1, C_2, \cdots , C_N$($1 ≤ C_a ≤ 100$)이 공백 하나로 구분되어 주어진다.

출력

첫 번째 줄에 정수 $a$를 정확히 $C_a$개 포함하는 모든 서로 다른 원형 정수열에 대해서 점수의 총합을 출력한다. 이 수는 매우 클 수 있으므로, $1\,000\,000\,007$로 나눈 나머지를 출력하도록 한다.

예제 입력 1

2
2 2

예제 출력 1

18

예제 입력 2

3
4 3 2

예제 출력 2

7830

예제 입력 3

4
4 4 4 4

예제 출력 3

818559048

예제 입력 4

5
1 2 3 4 5

예제 출력 4

342934740

예제 입력 5

6
7 8 9 10 11 12

예제 출력 5

609539975

힌트

첫 번째 예제에서 만들어지는 원형 정수열은 다음의 $6$가지이다:

  • $[1, 1, 2, 2]$: $4$점
  • $[1, 2, 1, 2]$: $1$점
  • $[1, 2, 2, 1]$: $4$점
  • $[2, 1, 1, 2]$: $4$점
  • $[2, 1, 2, 1]$: $1$점
  • $[2, 2, 1, 1]$: $4$점

그러므로 총 $18$점이다.

W3sicHJvYmxlbV9pZCI6IjE5MjkyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiaGkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCAkTCRcdWM3NzggXHVjNmQwXHVkNjE1IFx1YzgxNVx1YzIxOFx1YzVmNCAkW2hfMSwgaF8yLCBcXGNkb3RzICwgaF9MXSRcdWM3NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gJGhfaSRcdWM2NDAgJGhfe2krMX0kXHViMjk0IFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDJiOVx1YmNjNFx1ZDc4OCAkaF9MJFx1YWNmYyAkaF8xJFx1Yzc3NCZuYnNwO1x1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyOTQgXHVkNjE1XHVkMGRjXHViMmU0LiBcdWM3NzQgXHVjNmQwXHVkNjE1IFx1YzgxNVx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM4MTBcdWMyMThcdWIyOTQgXHVhYzE5XHVjNzQwJm5ic3A7XHVjMjE4XHViNGU0XHVjNzc0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJkODBcdWJkODRcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NzRcdWMxMWMgXHVhY2YxXHVkNTVjIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCAkaCA9IFsxLCAxLCAyLCAyLCAxLCAzLCAzLCAzLCAxLCAxXSQgXHVjNzc0XHViYTc0LCBcdWM4MTBcdWMyMThcdWIyOTQgJDQgXFx0aW1lcyAyIFxcdGltZXMgMSBcXHRpbWVzIDMgPSAyNCRcdWM4MTBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4kMSRcdWM3NzRcdWMwYzEgJE4kXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1YjljYyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWJhNzRcdWMxMWMsIFx1YzgxNVx1YzIxOCAkYSRcdWI5N2MgXHVjODE1XHVkNjU1XHVkNzg4ICRDX2EkXHVhYzFjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzZkMFx1ZDYxNSBcdWM4MTVcdWMyMThcdWM1ZjRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuIFx1YjQ1MCZuYnNwO1x1YzZkMFx1ZDYxNSBcdWM4MTVcdWMyMThcdWM1ZjQgJGgkXHVjNjQwICRoJiMzOTskXHVjNzc0IFx1YjJlNFx1Yjk3NFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDAgJGhfaSBcXG5lIGgmIzM5O19pJFx1Yzc3OCAkaSRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMTggJE4kKCQxICZsZTsgTiAmbGU7IDUwJClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRDXzEsIENfMiwgXFxjZG90cyAsIENfTiQoJDEgJmxlOyBDX2EgJmxlOyAxMDAkKVx1Yzc3NCBcdWFjZjVcdWJjMzEgXHVkNTU4XHViMDk4XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICRhJFx1Yjk3YyBcdWM4MTVcdWQ2NTVcdWQ3ODggJENfYSRcdWFjMWMgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0Jm5ic3A7XHViYWE4XHViNGUwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNmQwXHVkNjE1IFx1YzgxNVx1YzIxOFx1YzVmNFx1YzVkMCZuYnNwO1x1YjMwMFx1ZDU3NFx1YzExYyBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDFkXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsICQxXFwsMDAwXFwsMDAwXFwsMDA3JFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljMFx1YjI5NCBcdWM2ZDBcdWQ2MTUgXHVjODE1XHVjMjE4XHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1Yzc1OCAkNiRcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JFsxLCAxLCAyLCAyXSQ6ICQ0JFx1YzgxMDxcL2xpPlxyXG5cdDxsaT4kWzEsIDIsIDEsIDJdJDogJDEkXHVjODEwPFwvbGk+XHJcblx0PGxpPiRbMSwgMiwmbmJzcDsyLCAxXSQ6ICQ0JFx1YzgxMDxcL2xpPlxyXG5cdDxsaT4kWzIsIDEsIDEsIDJdJDogJDQkXHVjODEwPFwvbGk+XHJcblx0PGxpPiRbMiwgMSwgMiwgMV0kOiAkMSRcdWM4MTA8XC9saT5cclxuXHQ8bGk+JFsyLCAyLCAxLCAxXSQ6ICQ0JFx1YzgxMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YmJjMFx1Yjg1YyBcdWNkMWQgJDE4JFx1YzgxMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE5MjkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2lyY3VsYXIgQXJyYW5nZW1lbnQiLCJkZXNjcmlwdGlvbiI6IjxwPkFycmF5bG92ZXIgWmlndWkgaGFzICRuJCBwb3NpdGl2ZSBpbnRlZ2VycyAkY18xLCBjXzIsIFxcbGRvdHMsIGNfbiQuIEhlIG1hZGUgZXZlcnkgcG9zc2libGUgYXJyYXkgdGhhdCBjb250YWlucyBleGFjdGx5ICRjX2kkIGNvcGllcyBvZiBpbnRlZ2VyICRpJCBmb3IgZWFjaCAkaSQgZnJvbSAkMSQgdG8gJG4kLiBGb3IgZXhhbXBsZSwgd2hlbiAkbj0zJCwgJGNfMT00JCwgJGNfMj0zJCwgYW5kICRjXzM9MiQsIGhlIGhhdmUgbWFkZSBtYW55IGFycmF5cywgb25lIG9mIHdoaWNoIGlzIHRoZSBhcnJheSA8Y29kZT5bMSwxLDMsMywxLDIsMiwyLDFdPFwvY29kZT4uPFwvcD5cclxuXHJcbjxwPktvbyBpcyBhIGJpZyBmYW4gb2YgWmlndWkuIEhlIHdhbnRzIHRvIG1ha2UgdGhlIHNhbWUgYXJyYXlzIGFzIFppZ3VpLiBCdXQgdW5saWtlIFppZ3VpLCBoZSBsb3ZlcyA8c3Ryb25nPmNpcmN1bGFyPFwvc3Ryb25nPiZuYnNwO3RoaW5ncy4gVGh1cywgaGUgd2lsbCBtYWtlIGV2ZXJ5IGFycmF5IGNpcmN1bGFyLiBJbiBhIGNpcmN1bGFyIGFycmF5LCB0aGUgZmlyc3QgZWxlbWVudCBhbmQgdGhlIGxhc3QgZWxlbWVudCBhcmUgYWRqYWNlbnQuPFwvcD5cclxuXHJcbjxwPk1ha2luZyBhbiBhcnJheSBoYXMgYSBjZXJ0YWluIGNvc3QuIE1vcmUgc3BlY2lmaWNhbGx5LCB0aGUgY29zdCBvZiBtYWtpbmcgYW4gYXJyYXkgaXMgdGhlIHByb2R1Y3Qgb2Ygc2l6ZXMgb2YgYWRqYWNlbnQgZ3JvdXBzIG9mIGVxdWFsIHZhbHVlcy4gRm9yIGV4YW1wbGUsIHRoZSBhcnJheSA8Y29kZT5bMSwxLDMsMywxLDIsMiwyLDFdPFwvY29kZT4gY29udGFpbnMgZml2ZSBhZGphY2VudCBncm91cHMgb2YgZXF1YWwgdmFsdWVzOiB0d28gPGNvZGU+MTxcL2NvZGU+cywgdGhlbiB0d28gPGNvZGU+MzxcL2NvZGU+cywgdGhlbiBvbmUgPGNvZGU+MTxcL2NvZGU+LCB0aGVuIHRocmVlIDxjb2RlPjI8XC9jb2RlPnMsIGFuZCBmaW5hbGx5LCBvbmUgPGNvZGU+MTxcL2NvZGU+LiBUaGUgY29zdCBvZiBtYWtpbmcgdGhpcyBhcnJheSBpcyB0aGVyZWZvcmUgJDIgXFx0aW1lcyAyIFxcdGltZXMgMSBcXHRpbWVzIDMgXFx0aW1lcyAxID0gMTIkLjxcL3A+XHJcblxyXG48cD5JbiBhIGNpcmN1bGFyIGFycmF5LCBpZiB0aGUgdmFsdWVzIG9mIHRoZSBmaXJzdCBlbGVtZW50IGFuZCB0aGUgbGFzdCBlbGVtZW50IGFyZSBlcXVhbCwgdGhlaXIgZ3JvdXBzIGFyZSBtZXJnZWQuIFRodXMsIHRoZSBjb3N0IG9mIG1ha2luZyBhIGNpcmN1bGFyIGFycmF5IDxjb2RlPlsxLDEsMywzLDEsMiwyLDIsMV08XC9jb2RlPiBpcyAkKDIgKyAxKSBcXHRpbWVzIDIgXFx0aW1lcyAxIFxcdGltZXMgMyA9IDE4JC48XC9wPlxyXG5cclxuPHA+Q2FsY3VsYXRlIHRoZSBzdW0gb2YgdGhlIGNvc3RzIG9mIGFsbCBjaXJjdWxhciBhcnJheXMgS29vIHdpbGwgbWFrZS4gTm90ZSB0aGF0LCBpbiBhIGNpcmN1bGFyIGFycmF5LCB0aGUgaW5kZXggb2YgZWFjaCBlbGVtZW50IGlzIHN0aWxsIGltcG9ydGFudCwganVzdCBsaWtlIGluIGEgcmVndWxhciBhcnJheS4gU28sIGZvciBleGFtcGxlLCA8Y29kZT5bMSwyLDEsMl08XC9jb2RlPiBhbmQgPGNvZGU+WzIsMSwyLDFdPFwvY29kZT4gYXJlIGRpZmZlcmVudCBjaXJjdWxhciBhcnJheXMuIEFzIHRoZSB0b3RhbCBjb3N0IG1heSBiZSB2ZXJ5IGxhcmdlLCBjYWxjdWxhdGUgdGhpcyBzdW0gbW9kdWxvICQxMF45ICsgNyQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyAkbiQsIHRoZSBudW1iZXIgb2YgZGlzdGluY3QgaW50ZWdlcnMgdG8gdXNlICgkMiBcXGxlcSBuIFxcbGVxIDUwJCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkbiQgcG9zaXRpdmUgaW50ZWdlcnMgJGNfMSwgY18yLCBcXGxkb3RzLCBjX24kLCB3aGVyZSAkY19pJCBpcyB0aGUgbnVtYmVyIG9mIG9jY3VycmVuY2VzIG9mIGludGVnZXIgJGkkIGluIGVhY2ggZGVzaXJlZCBhcnJheSAoJDEgXFxsZSBjX2kgXFxsZSAxMDAkKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgc3VtIG9mIGNvc3RzIG9mIGFsbCBvZiBhbGwgY2lyY3VsYXIgYXJyYXlzIEtvbyB3aWxsIG1ha2UsIG1vZHVsbyAkMTBeOSArIDckLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgdGhlIGZpcnN0IGV4YW1wbGUsIHdlIGNhbiBtYWtlIHNpeCBjaXJjdWxhciBhcnJheXMuIEhlcmUgYXJlIHRoZSBhcnJheXMgYW5kIHRoZWlyIGNvc3RzOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48Y29kZT5bMSwxLDIsMl06IDQgWzEsMiwxLDJdOiAxIFsxLDIsMiwxXTogNDxcL2NvZGU+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxjb2RlPlsyLDEsMSwyXTogNCBbMiwxLDIsMV06IDEgWzIsMiwxLDFdOiA0PFwvY29kZT48XC9wPlxyXG5cclxuPHA+VGhlIHN1bSBvZiBhbGwgdGhlIGNvc3RzIGlzICQxOCQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d