따스나라에는 왼쪽부터 오른쪽까지 개의 산이 있다. 번째 산의 높이는 이다.
다다스 왕은 서로 다른 산을 정확히 개 골라 각 산의 정상에 중계기를 하나씩 설치하려고 한다.
이고 번째 산과 번째 산에 중계기가 설치되어 있다고 하자. 다음 조건을 만족하면 두 중계기는 직접 통신할 수 있다.
와 가 이웃한 위치라면 두 중계기는 항상 직접 통신할 수 있다.
설치된 중계기를 정점으로 하고, 직접 통신할 수 있는 두 중계기 사이에 간선을 이은 무향 그래프를 생각하자. 모든 중계기 쌍이 개 이하의 간선을 거쳐 정보를 전달할 수 있어야 한다. 즉, 이 그래프는 연결되어 있고 지름이 이하여야 한다. 중계기가 하나뿐인 그래프의 지름은 으로 정의한다.
조건을 만족하도록 중계기를 설치하는 방법의 수를 구하여라. 두 설치 방법은 중계기를 설치한 산의 집합이 다르면 서로 다른 방법이다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 설치 방법의 수를 으로 나눈 나머지를 한 줄에 출력한다.
각 케이스는 다음과 같은 형식으로 주어진다.
| 4 | 30 | . |
| 5 | 15 | 추가적인 제약이 없다. |
