시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB168147433630.713%

문제

다솜이는 자신의 목걸이를 구슬을 이용해서 만들려고 한다. 다솜이는 구슬을 N종류 가지고 있다. 서로 다른 종류의 구슬은 색이 다르다. 다솜이는 구슬을 실에 껴서 목걸이를 만들려고 한다. 무작정 껴도 상관없겠지만, 워낙 미적감각이 뛰어난 다솜이는 임의의 연속된 3개의 구슬의 색을 모두 다르게 하려고 한다.

예를 들어, 다솜이가 1번 구슬을 2개, 2번 구슬을 1개, 3번 구슬을 1개 가지고 있다고 하자. 1번 구슬이 초록, 2번 구슬이 파랑, 3번 구슬이 빨강이라고 하면, 연속된 3개의 구슬이 같은 색이면 안되기 때문에, 초록구슬을 반드시 목걸이의 끝에 있어야 한다. 따라서 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수는 초록-빨강-파랑-초록 또는 초록-파랑-빨강-초록 총 2가지이다.

반드시 가지고 있는 모든 구슬을 이용해야 하며, 목걸이는 원형이 아니라 직선이다. 다시말하면, 처음 구슬과 마지막 구슬은 이어져있는 것이 아니다.

다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, 둘째 줄에는 2번 구슬, 이런 형식이다. 각각의 구슬은 10개보다 작거나 같은 자연수이다. 그리고, 구슬의 총 개수의 합은 35를 넘지 않는다.

출력

첫째 줄에 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 출력한다.

예제 입력 1

3
1
1
1

예제 출력 1

6

예제 입력 2

4
1
1
1
1

예제 출력 2

24

예제 입력 3

3
2
1
1

예제 출력 3

2

예제 입력 4

3
3
1
1

예제 출력 4

0

예제 입력 5

3
3
2
2

예제 출력 5

2

출처