$\prod_{i=1}^N(R_i-L_i+1)$개의 트리

1번 정점을 루트로 하는 정점 $N$개의 트리가 주어진다. 각 정점 $i$에 음이 아닌 정수 $a_i$를 정한다.

$a_i$들은 모든 $1 \le i \le N$에 대해 다음 두 조건을 만족해야 한다.

• $a_i \le p_i$
• $i$번 정점의 서브트리에 속한 정점 $j$들의 $a_j$를 모두 더한 값을 $S_i$라고 하면, $S_i \ge q_i$

위 조건을 만족하는 $(a_1, a_2, \ldots, a_N)$에 대해 $\sum_{i=1}^N c_i a_i$의 최솟값을 $f(c_1, c_2, \ldots, c_N)$으로 정의한다.

다음 값을 $998\,244\,353$으로 나눈 나머지를 구하라.

$\sum_{c_1=L_1}^{R_1}\sum_{c_2=L_2}^{R_2}\cdots\sum_{c_N=L_N}^{R_N}f(c_1,c_2,\cdots,c_N)$

첫 줄에 정점의 개수 $N$이 주어진다. ($1 \le N \le 250$)

둘째 줄부터 $N-1$개의 줄에 트리 간선 정보가 주어진다. $i$번째 줄에는 두 정수 $s_i$, $e_i$가 공백으로 구분되어 주어지며, 이는 $s_i$와 $e_i$를 잇는 간선이 존재한다는 뜻이다. ($1 \le s_i, e_i \le N$)

$1 \le i \le N$에 대해, $(N+i)$번째 줄에는 $p_i$, $q_i$, $L_i$, $R_i$가 공백으로 구분되어 주어진다. ($1 \le L_i \le R_i \le 250$; $0 \le p_i, q_i \le 250$; $\sum_{i=1}^N p_i \le 250$)

주어진 그래프는 트리이며, 조건을 만족하는 $(a_1, a_2, \ldots, a_N)$이 존재하는 입력만 주어진다.

문제에 주어진 값을 $998\,244\,353$으로 나눈 나머지를 출력한다. $998\,244\,353=119\times 2^{23}+1$은 소수이다.

$j$번 정점이 $i$번 정점의 서브트리에 포함되는 경우는 $j=i$이거나 $i$번 정점이 $j$번 정점의 조상인 경우이다.