리카와 장군들

오늘 리카는 전략 게임을 하고 있다. 게임의 첫 단계는 이미 끝났고, 그녀는 자신의 나라를 세웠다.

리카의 나라에는 $n$개의 도시가 있고, 이 도시들은 $n-1$개의 양방향 도로로 연결되어 있다. 어떤 두 도시든 도로를 따라 서로 갈 수 있다. 리카는 이 도시들을 $n$명의 충성스러운 장군에게 나누어 주기로 했다. 장군들은 공적이 작은 순서대로 1부터 $n$까지 번호가 붙어 있다. 처음에 리카는 $i$번째 도시를 $p_i$번 장군에게 주기로 했다. 여기서 $p_1, p_2, \dots, p_n$은 길이 $n$의 순열이다.

리카는 장군들을 모두 소집해 이 초기 계획을 보여준다. 장군들은 다음 두 조건을 만족할 때에만 도시를 서로 맞바꿀 수 있다. 장군 $u$가 도시 $a$를, 장군 $v$가 도시 $b$를 갖고 있을 때, 아래 조건이 모두 성립하면 두 장군은 도시를 교환할 수 있다.

• 두 장군의 공적이 비슷하다. 즉 $|u-v|$가 1이어야 한다.
• 두 도시의 위치가 가깝다. 즉 도시 $a$와 도시 $b$ 사이에 도로가 있어야 한다.

교환 과정에서 한 장군은 도시를 여러 번 바꿀 수 있고, 한 도시도 여러 장군 사이에서 옮겨 갈 수 있다.

예상대로 장군들 사이에 다툼이 벌어졌다. 도시의 소유권을 정하려면 오랜 시간이 걸릴 것 같다. 리카는 이 상황이 지루하다. 재미로, 가능한 분배 계획의 수를 세어 달라고 한다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \leq t \leq 2 \times 10^5$)가 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 개수 $n$ ($1 \leq n \leq 2 \times 10^5$)이 주어진다. 이어서 $n-1$개의 줄에 정수 $u$와 $v$ ($1 \leq u,v \leq n$)가 주어지며, 도시 $u$와 도시 $v$ 사이에 도로가 있음을 뜻한다.

마지막 줄에는 초기 분배 계획 $p_i$ ($1 \leq p_i \leq n$)가 $n$개 주어진다. 입력은 $p_1, p_2, \dots, p_n$이 길이 $n$의 순열임을 보장한다. 모든 테스트 케이스의 $n$의 합은 $2 \times 10^5$ 이하이다.

각 테스트 케이스마다 가능한 분배 계획의 수를 한 줄에 출력한다. 답이 매우 클 수 있으므로 $998244353$으로 나눈 나머지를 출력한다.

간단히 나타내기 위해 분배 계획을 $[a_1, \dots, a_n]$으로 표기한다. 여기서 $a_i$는 $i$번 장군이 갖는 도시이다. 가능한 분배 계획은 모두 7가지이다.

• $[2,1,5,4,3]$: 교환 없이 그대로인 경우.
• $[1,2,5,4,3]$: 장군 $(1,2)$ 사이에서 교환한 경우.
• $[2,1,5,3,4]$: 장군 $(4,5)$ 사이에서 교환한 경우.
• $[1,2,5,3,4]$: 장군 $(4,5)$, 그다음 $(1,2)$ 순서로 교환한 경우.
• $[2,1,3,5,4]$: 장군 $(4,5)$, 그다음 $(3,4)$ 순서로 교환한 경우.
• $[1,2,3,5,4]$: 장군 $(4,5)$, $(3,4)$, $(1,2)$ 순서로 교환한 경우.
• $[2,3,1,5,4]$: 장군 $(4,5)$, $(3,4)$, $(2,3)$ 순서로 교환한 경우.