이진 트리의 사전순 번호

루트가 있는 트리에서 모든 정점이 자식을 $0$개, $1$개 또는 $2$개 가지며, 자식이 있을 때 그 자식이 왼쪽 자식인지 오른쪽 자식인지 구분되는 트리를 이진 트리라고 하자. 따라서 자식이 하나뿐인 정점도 그 자식이 왼쪽인지 오른쪽인지에 따라 서로 다른 트리가 된다.

트리의 높이는 루트에서 어떤 잎까지 가는 경로 중 가장 긴 경로에 놓인 정점의 개수이다. 빈 트리의 높이는 $0$이다.

이진 트리들 사이에는 다음과 같은 사전순 순서가 정의된다. 트리 $A$가 트리 $B$보다 사전순으로 작다는 것은 다음 중 하나가 성립하는 경우이다.

• $A$의 높이가 $B$의 높이보다 작다.
• $A$와 $B$의 높이가 같고, 다음 중 하나가 성립한다.
  • $A$의 왼쪽 부분 트리가 $B$의 왼쪽 부분 트리보다 사전순으로 작다.
  • $A$와 $B$의 왼쪽 부분 트리가 같고, $A$의 오른쪽 부분 트리가 $B$의 오른쪽 부분 트리보다 사전순으로 작다.

어떤 정점에 왼쪽 자식이 없으면 그 정점의 왼쪽 부분 트리는 빈 트리로 본다. 오른쪽 자식이 없는 경우도 마찬가지이다.

두 트리 $A$와 $B$가 서로 다르고 $A$가 $B$보다 사전순으로 작지 않으면, $A$는 $B$보다 사전순으로 크다.

이 순서에 따라 모든 이진 트리에 번호를 매긴다. 정점이 하나뿐인 트리의 번호는 $1$이다. 주어진 트리의 번호를 $1\,000\,000\,000$으로 나눈 나머지를 구하여라.

첫째 줄에 트리의 개수 $t$ ($1 \le t \le 1\,000$)가 주어진다.

이어서 $t$개의 트리 설명이 주어진다. 각 트리 설명의 첫째 줄에는 정점의 개수 $n$ ($1 \le n \le 2\,000$)이 주어진다. 정점은 $1$번부터 $n$번까지 번호가 매겨져 있으며, $1$번 정점이 루트이다.

그다음 $n$개의 줄에 각 정점의 자식 정보가 주어진다. $i$번째 줄에는 두 정수 $l_i$와 $r_i$가 주어지며, 각각 $i$번 정점의 왼쪽 자식과 오른쪽 자식의 번호이다. $i$번 정점에 왼쪽 자식이 없으면 $l_i = -1$이고, 오른쪽 자식이 없으면 $r_i = -1$이다.

정확히 $t$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 트리의 번호를 $1\,000\,000\,000$으로 나눈 나머지를 출력한다.