서기 10^5년, 인류는 우주를 자유롭게 돌아다닐 수 있는 것은 물론, 멀티버스의 존재 또한 발견했고 멀티버스로 이동도 할 수 있게 되었다.

인류는 지금 총 N개의 은하를 관리하고 있다. 하지만 우주는 너무나도 광활하기 때문에 고속 이동 장치가 필요했고, 그에 따라 N-1개의 고속 이동 장치를 배치하여 어떤 두 은하 사이에도 이동이 가능하게 만들었다.

멀티버스는 지금의 우주의 모양과 정확히 같은 다른 우주로, 위에서 언급한 고속 이동 장치의 배열도 같다.

하지만 멀티버스 간의 여행에는 제약이 있다. 지금이 i번 멀티버스라면, 우리는 i+1번 멀티버스로만 이동할 수 있다. 즉, 멀티버스 간의 이동은 단방향이다.

멀티버스 간의 이동은 굉장히 어렵기 때문에, 정해진 은하에서 정해진 은하로만 이동할 수 있다. 즉, i-1번 멀티버스의 Ai번 은하에서 i번 멀티버스의 Bi번 은하로만 이동할 수 있다.

또, 멀티버스가 발견된지 얼마 안됐기 때문에, 이동할 수 있는 멀티버스의 수는 제한적이다. 지금 위치한 우주가 0번 멀티버스라면, 우리는 최대 D번 멀티버스까지밖에 이동할 수 없다.

정올이와 한컴이는 모험가이다. 그러기에 서로 누가 더 모험을 잘하는지 경쟁하려 한다. 정올이부터 시작해서 번갈아가면서, 이동할 다음 은하를 선택하여 움직인다. 단, 전에 한번 방문했던 은하는 다시 방문하지 않으며, 다른 멀티버스의 은하는 다른 은하로 취급한다. 만약 더 이상 움직이지 못한다면 그 사람이 패배한다.

시작점이 0번 멀티버스의 1번 은하일 때, 정올이가 무슨 일이 있어도 항상 승리할 수 있는 (A1, ..., AD, B1, ..., BD) 쌍의 개수를 구하시오.

답이 매우 커질 수 있으므로 10^9+7로 나눈 나머지를 대신 출력하여라.

#5688 upload 11 done - how_to_reg -

멀티버스 timer 1s memory 1024MB

#5688

멀티버스 1s 1024MB