교토 대학교에는 상징적인 나무가 하나 있습니다. 이 나무에 감명받은 K군은 이 나무를 복사하여 $N$개의 정점을 가진 루트 있는 트리로 만들었습니다.

트리의 정점에는 $1, 2, \dots, N$의 번호가 매겨져 있으며, 루트는 정점 $1$입니다. $i$번째 간선은 정점 $u_i$와 $v_i$를 연결합니다.

단순히 나무를 복사하는 것은 재미없다고 생각한 K군은 트리의 각 정점에 음이 아닌 정수를 적어 다음 조건들을 만족시키려 합니다.

조건

• 루트에 적힌 정수는 $K$입니다.
• 루트가 아닌 각 정점에 적힌 정수는 그 부모 정점에 적힌 정수보다 작거나 같습니다.

트리의 정점에 정수를 적는 가능한 방법의 수를 $998244353$으로 나눈 나머지를 구하세요.

정점에 정수를 적는 두 방법은, 어떤 정점에 적힌 정수가 서로 다른 정점이 존재할 경우에만 서로 다른 것으로 간주합니다.

입력

첫 번째 줄에는 공백으로 구분된 정수 $N, K$가 주어집니다. ($2 \le N \le 3000, 1 \le K \le 10^9$)

다음 $N - 1$개의 줄에는 트리의 간선을 나타내는 정수 $u_i, v_i$가 공백으로 구분되어 주어집니다.

출력

정답을 $998244353$으로 나눈 나머지를 출력하세요.

예제

입력 1

5 1
1 2
1 3
3 4
3 5

출력 1

10

입력 2

16 16
15 14
15 11
7 10
14 2
4 6
14 16
5 3
1 5
12 11
5 7
2 9
13 10
5 14
9 6
8 1

출력 2

623173536

참고

첫 번째 예제에서, 정점 $1, 2, 3, 4, 5$에 정수를 할당하는 다음 10가지 방법이 조건을 만족합니다.

• 1, 0, 0, 0, 0
• 1, 0, 1, 0, 0
• 1, 0, 1, 0, 1
• 1, 0, 1, 1, 0
• 1, 0, 1, 1, 1
• 1, 1, 0, 0, 0
• 1, 1, 1, 0, 0
• 1, 1, 1, 0, 1
• 1, 1, 1, 1, 0
• 1, 1, 1, 1, 1