제노는 생일 파티를 열 예정이다. 파티에는 그가 사장으로 있는 회사의 직원들 중 몇몇을 초대하기로 했다. 제노를 포함하여 회사의 직원들은 1번부터 N번까지 고유한 사원번호를 갖고 있으며 각 사원들은 어떤 타입의 농담을 하는데 그 농담 타입을 Vi 로 나타낸다. 또한 제노를 제외하고 모든 사원은 정확히 한 명의 직접적인 상사가 있다.

제노는 회사의 사장이기 때문에 상사가 없으며 사원번호도 1번이다. 그리고 모든 사원의 직접적이거나 간접적인 상사이다.

생일 파티에 참석하는 모든 사람의 농담 타입들을 모아 농담 세트를 구성하는데 각각의 직원은 다음과 같은 규칙을 따라야 한다.

- 생일 파티에 같은 타입의 농담을 하는 사람이 두 명 이상일 수 없다.

- 제노를 제외하고 직접적인 상사가 초대되지 않는 직원은 초대될 수 없다.

- 어떤 사원 X가 파티에 참석한 모든 그의 직간접적인 부하 직원들과 함께 농담 세트를 연속적인 번호들로 구성할 수 없다면 초대될 수 없다.

인접한 원소들을 오름차순으로 정렬했을 때 1씩 증가하는 상태라면 연속적이라고 할 수 있다. 예를 들면 (3, 1, 2), (5, 1, 2, 4, 3) 등이 있다.

제노는 사원정보가 주어졌을 때 제약사항을 만족하는 얼마나 많은 서로 다른 농담 세트가 있는지 알고 싶다. 이를 구하는 프로그램을 작성해 보자.

입력 예 1에서 서로 다른 농담 세트는 {2}, {2, 3}, {2, 3, 4}, {1, 2, 3, 4}, {1, 2}, {1, 2, 3} 이다.

입력 예 2에서 서로 다른 농담 세트는 {3}, {3, 4}, {3, 4, 5}이다. {4, 6}은 연속된 수가 아니므로 가능한 경우의 수에 포함 될 수 없다.

입력 예 3에서 서로 다른 농담 세트는 {5}, {4, 5}, {3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}, {5, 6}, {4, 5, 6}, {3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6}이다.

#2981 upload 10회 done 5회 how_to_reg 5명

파티초대(UZASTOPNI) timer 1초 memory 32MB

#2981

파티초대(UZASTOPNI) 1초 32MB