레이팅 미적용가뭄으로 농부 존의 목초지에 풀이 다 말라버렸다. 몇 시간의 절망과 고민 끝에, 농부 존은 소중한 소들에게 먹일 옥수수를 구입한다는 기발한 아이디어를 떠올린다.
농부 존의 \(N\)마리(\(1 \leq N \leq 100\)) 소들은 한 줄로 서 있으며, 줄에서 \(i\)번째 소의 배고픔 수치는 음이 아닌 정수 \(h_i\)이다. 소들은 사회적인 동물이라 함께 먹기를 고집하기 때문에, 농부 존이 소들의 배고픔 수치를 줄일 수 있는 유일한 방법은 인접한 두 소 \(i\)와 \(i+1\)을 선택해 각각에게 옥수수 한 자루씩을 먹여 각자의 배고픔 수치를 1씩 줄이는 것이다.
농부 존은 모든 소의 배고픔 수치가 같은 음이 아닌 값이 될 때까지 소들에게 먹이를 주고 싶다. 그는 소들의 정확한 배고픔 수치는 모르지만, 각 소의 배고픔 수치에 대한 상한은 알고 있다. 구체적으로, \(i\)번째 소의 배고픔 수치 \(h_i\)는 최대 \(H_i\)(\(0\le H_i\le 1000\))이다.
이 상한들과 모순되지 않으면서 농부 존이 목표를 달성할 수 있는 배고픔 수치의 \(N\)-튜플 \([h_1,h_2,\ldots,h_N]\)의 개수를 \(10^9+7\)로 나눈 나머지를 구하는 것이 당신의 일이다.
출제자: Arpan Banerjee and Benjamin Qi
배점
짝수 번호 테스트에서 \(N\)은 짝수이고, 홀수 번호 테스트에서 \(N\)은 홀수이다.
- 테스트 3과 4는 \(N\le 6\)과 \(H_i \le 10\)을 만족한다.
- 테스트 5-10은 \(N\le 50\)과 \(H_i \le 100\)을 만족한다.
- 테스트 11-20은 추가 제약이 없다.
출제자: Arpan Banerjee and Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(H_1,H_2,\ldots,H_N\)이 주어진다.
배고픔 수치의 \(N\)-튜플의 개수를 \(10^9+7\)로 나눈 나머지를 출력한다.
3
9 11 7241There are \((9+1)\cdot (11+1)\cdot (7+1)\) \(3\)-tuples \(h\) that are consistent with
\(H\).
One of these tuples is \(h=[8,10,5]\). In this case, it is possible to make all
cows have equal hunger values: give two bags of corn to both cows \(2\) and \(3\),
then give five bags of corn to both cows \(1\) and \(2\), resulting in each cow
having a hunger level of \(3\).
Another one of these tuples is \(h=[0,1,0]\). In this case, it is impossible to
make the hunger levels of the cows equal.
4
6 8 5 9137