배열 순서의 수

오늘 캐럴은 쉬는 날이다. 하지만 이 화창한 봄날에도 그녀는 쉬지 않고 스크럴과의 전투를 대비해 훈련한다. 낯선 곳에서 길을 빨리 찾는 능력은 중요한 기술 가운데 하나다. 이 능력을 갈고닦기 위해 캐럴은 스승인 욘로그를 초대했다.

캐럴과 욘로그는 다음 게임을 한다. 먼저 욘로그가 종이에 스크럴 은신처의 지도를 그린다. 지도에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 방이 있다. 일부 방 쌍은 양방향 통로로 연결된다. 은신처는 어느 방에서든 통로를 따라 다른 모든 방으로 갈 수 있도록 설계되어 있다. 게임이 너무 복잡해지지 않도록 욘로그는 정확히 $n - 1$개의 통로만 그린다. 즉, 은신처 지도는 트리다.

스크럴은 방 사이로 화물을 옮기는 데 특수 로봇을 쓴다. 로봇은 단순해서 은신처에서 길을 잘 찾지 못한다. 그래서 스크럴은 통로마다 로봇이 이동할 수 있는 방향을 정확히 하나씩 정했다.

욘로그는 지도를 그린 뒤 각 통로에 로봇이 움직이는 방향을 표시한다. 즉, 그린 트리의 간선에 방향을 부여한다.

캐럴은 지도를 정리하기 위해 모든 방 번호를 어떤 순서로든 한 번씩 적은 목록을 만들어야 한다. 이 목록은 다음 조건을 만족해야 한다. 어떤 통로에서든 로봇은 목록에서 앞에 있는 방에서 뒤에 있는 방으로 이동한다. 더 정확히 말하면, 로봇이 방 $p_i$에서 방 $p_j$로 통로를 따라 이동할 수 있다면 $i < j$이어야 한다. 이 목록은 순열 $p_1 p_2 \ldots p_n$이다.

캐럴이 과제에 매달리는 동안 욘로그는 이 조건을 만족하는 순열이 모두 몇 개인지 궁금해졌다. 답이 매우 클 수 있으므로 욘로그는 $998\,244\,353$으로 나눈 나머지만 알려 달라고 부탁했다.

첫째 줄에 욘로그가 그린 은신처의 방 개수 $n$이 주어진다 ($1 \le n \le 3\,000$).

이어지는 $n - 1$개의 줄에는 통로로 직접 연결된 두 방의 번호 $a$, $b$가 주어진다. 로봇은 이 통로를 방 $a$에서 방 $b$의 방향으로 이동한다.

은신처는 트리임이 보장된다. 즉, 어느 방에서든 통로를 따라 다른 모든 방에 갈 수 있으며, 이때 이동 방향은 로봇의 이동 방향과 반대여도 된다.

조건을 만족하는 서로 다른 순열 $p_1 p_2 \ldots p_n$의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 번째 테스트에서 캐럴은 $\{1, 2, 3\}$ 또는 $\{1, 3, 2\}$ 두 개의 순열을 쓸 수 있다.

두 번째 테스트에서 캐럴은 $\{2, 3, 1, 4\}$, $\{2, 3, 4, 1\}$, $\{2, 4, 3, 1\}$ 세 개의 순열을 쓸 수 있다.