어떤 중세 역사서에 따르면, 정올국은 n개의 영토로 이루어져 있었다.

정올국은 지형상 길을 많이 만들 수 없어서, (n-1)개의 길로 모든 영토를 다 연결해 놓았다.

어떤 두 영토를 고르더라도, 한 영토에서 다른 영토로 가는 경로는 유일했다고 전해진다.

정올국의 국왕인 호는 아들과 딸인 혁과 희에게 정올국의 영토들을 분배해 주기로 했었다.

분배해 준다는 것은 n개의 영토 중 몆 개를 혁의 영토로, 나머지를 희의 영토로 정해준다는 뜻이다.

사실, 혁과 희는 사이가 별로 좋지 않았다고 한다.

국왕 호가 몇 번이고 각각 다른 방식으로 영토를 분배해 보았지만,

그때마다 혁과 희가 전쟁을 일으켜서 영토 분배를 번복하던 일이 3번이나 있었다.

3차 정올 전쟁이 일어나서 또다시 국왕 호가 전쟁을 말리고 영토를 회수할 때 즈음,

국왕 호의 충실한 신하인 환이 다음과 같은 사실을 알아냈다.

형제들은 “약한 영토”를 발견하면 전쟁을 일으키는데, 그 약한 영토란 다음과 같이 정의된다:

다른 이웃한 영토 중 자신과 같은 소속의 영토가 하나도 없는 영토를 약한 영토라고 한다.

이런 약한 영토가 하나도 없게 영토를 분배한다면, 4차 정올 전쟁이 일어나지 않을 것이라는 것이 환의 발견이다.

국왕 호는 드디어 안도의 한숨을 내쉬며, 갑자기 환에게 다음과 같은 질문을 던졌다.

국왕인 자신이 영토 분배를 했을 경우 4차 정올 전쟁이 일어나지 않는 경우의 수가 얼마나 될까? 하고 말이다.

충신인 환이 당황하며, 사흘 안에 알아오겠다고 대답했으나 컴퓨터를 쓸 줄 모르는 환에게는 막막한 과제이다.

어서 그 질문에 대한 답을 하는 프로그램을 작성하여 타임머신을 타고 환에게 넘겨주도록 하자.

답이 매우 클 수 있으므로, 10^<9 + 7로 나눈 나머지를 출력하라.

참고: 한 자식에게 모든 영토를 다 주는 경우도 가능하다.

정올 전쟁 timer 1s memory 256MB

정올 전쟁 1s 256MB