Tree
Contest: Codeforces Round 499 (Div. 1)
Difficulty rating: 3400
Tags: fft, graphs, trees

The Main Martian Tree grows on Mars. It is a binary tree (a rooted tree, with no more than two sons at each vertex) with $$$n$$$ vertices, where the root vertex has the number $$$1$$$. Its fruits are the Main Martian Fruits. It's summer now, so this tree does not have any fruit yet.

Autumn is coming soon, and leaves and branches will begin to fall off the tree. It is clear, that if a vertex falls off the tree, then its entire subtree will fall off too. In addition, the root will remain on the tree. Formally: the tree will have some connected subset of vertices containing the root.

After that, the fruits will grow on the tree (only at those vertices which remain). Exactly $$$x$$$ fruits will grow in the root. The number of fruits in each remaining vertex will be not less than the sum of the numbers of fruits in the remaining sons of this vertex. It is allowed, that some vertices will not have any fruits.

Natasha wondered how many tree configurations can be after the described changes. Since this number can be very large, output it modulo $$$998244353$$$.

Two configurations of the resulting tree are considered different if one of these two conditions is true:

- they have different subsets of remaining vertices;
- they have the same subset of remaining vertices, but there is a vertex in this subset where they have a different amount of fruits.

Input format:
The first line contains two integers: $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le x \le 10^{18}$$$) — the size of the tree and the number of fruits in the root.

The $$$i$$$-th of the following $$$(n-1)$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — vertices connected by the $$$i$$$-th edge of the tree.

It is guaranteed that the input data describes a correct binary tree with the root at the vertex $$$1$$$.

Output format:
Print one number — the number of configurations of the resulting tree modulo $$$998244353$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 256.0 MB

Note:
Consider the first example.

There are $$$2$$$ fruits at the vertex $$$1$$$. The following $$$13$$$ options are possible:

- there is no vertex $$$2$$$, there is no vertex $$$3$$$;
- there is no vertex $$$2$$$, there are no fruits at the vertex $$$3$$$;
- there is no vertex $$$2$$$, there is $$$1$$$ fruit at the vertex $$$3$$$;
- there is no vertex $$$2$$$, there are $$$2$$$ fruits at the vertex $$$3$$$;
- there are no fruits at the vertex $$$2$$$, there is no vertex $$$3$$$;
- there are no fruits at the vertex $$$2$$$, there are no fruits at the vertex $$$3$$$;
- there are no fruits at the vertex $$$2$$$, there is $$$1$$$ fruit at the vertex $$$3$$$;
- there are no fruits at the vertex $$$2$$$, there are $$$2$$$ fruits at the vertex $$$3$$$;
- there is $$$1$$$ fruit at the vertex $$$2$$$, there is no vertex $$$3$$$;
- there is $$$1$$$ fruit at the vertex $$$2$$$, there are no fruits at the vertex $$$3$$$;
- there is $$$1$$$ fruit at the vertex $$$2$$$, there is $$$1$$$ fruit at the vertex $$$3$$$;
- there are $$$2$$$ fruits at the vertex $$$2$$$, there is no vertex $$$3$$$;
- there are $$$2$$$ fruits at the vertex $$$2$$$, there are no fruits at the vertex $$$3$$$.

Consider the second example. There are $$$5$$$ fruits at the vertex $$$1$$$. The following $$$7$$$ options are possible:

- there is no vertex $$$2$$$;
- there are no fruits at the vertex $$$2$$$;
- there is $$$1$$$ fruit at the vertex $$$2$$$;
- there are $$$2$$$ fruits at the vertex $$$2$$$;
- there are $$$3$$$ fruits at the vertex $$$2$$$;
- there are $$$4$$$ fruits at the vertex $$$2$$$;
- there are $$$5$$$ fruits at the vertex $$$2$$$.

Example input:
3 2
1 2
1 3

Example output:
13

Example input:
2 5
1 2

Example output:
7

Editorial:
Let $$$b_v = a_v - \sum{a_{to}}$$$, (for each $$$(v, to)$$$, such that $$$to$$$ — is a son of $$$v$$$ and tree have both vertices $$$v$$$ and $$$to$$$), then all that we need is $$$b_v \geq 0$$$ and $$$\sum{b_v} = x$$$, so for fixed subset of vertices number of ways to arrange weights is just number of ways to partite $$$x$$$ into such number of parts.
So let $$$f_i$$$ be number of ways to choose connected subtree of $$$i$$$ vertices, that contains vertex $$$1$$$, then answer is $$$\sum{f_i C_{x+i-1}^{i-1}}$$$.
Then we need to calculate $$$f_i$$$ for each $$$1 \leq i \leq n$$$, and calculate $$$C_{x+i-1}^{i-1}$$$ for each $$$1 \leq i \leq n$$$.
Let's use generating functions to calc $$$f_i$$$.
Let $$$dp_v$$$ be generating function of $$$\sum{f_i \cdot x^i}$$$, (if we will assume that $$$v$$$ — root and we will look only at vertices inside subtree of $$$v$$$).
Then if vertex $$$v$$$ — leaf, then $$$dp_v = x + 1$$$, if this vertex have one son, $$$dp_v = dp_{to} x + 1$$$, and if two, then $$$dp_v = dp_l dp_r x + 1$$$.
Then let maintain $$$dp_v$$$ as a sequence of polynomials $$$a_1, a_2, \ldots, a_k$$$, что $$$dp_v = (((a_1 + 1) a_2 + 1) \ldots) a_k + 1$$$).
Then if we have the representation of $$$dp_v$$$ in such format, we can find the exact value of polynomial in the sum of sizes of polynomials $$$\cdot \log^2{n}$$$.
For it you can note, that $$$dp_v$$$ is just $$$a_1 a_2 a_3 \ldots a_k + a_2 a_3 \ldots a_k + \ldots + a_k + 1$$$.
And then with FFT you can calculate value and multiplication for left half ($$$P_l(x)$$$ и $$$Q_l(x)$$$), and for right half ($$$P_r(x)$$$ и $$$Q_r(x)$$$).
Then $$$P(x) = (P_l(x) - 1) Q_r(x) + P_r(x)$$$, а $$$Q(x) = Q_l(x) Q_r(x)$$$.
So, you can calculate exact value of $$$dp_v$$$ in $$$T(n) = 2T(n/2) + O(n \log {n}) = O(n \log^2 {n})$$$ (Where $$$n$$$ is sum of sizes of polynomials).
Then if $$$v$$$ — leaf just add $$$x$$$ into the sequence of polynomials.
If $$$v$$$ have one son, then add $$$x$$$ into the sequence of polynomials of a son, and take his sequence as a sequence for vertex $$$v$$$.
And if $$$v$$$ have two sons, Let's take a son with the smaller size of a subtree, find its exact value as written, and add it into the sequence of another son.
Sum of sizes of smaller subtrees is $$$O(n \log {n})$$$, so we can find $$$f$$$ in $$$O(n \log^3{n})$$$.
Note, that you can find similar value when the tree is not binary too, for it you can find the exact value of all children without largest, and multiply it in $$$O(n \log^2 (n))$$$ with D&C.
To calculate $$$C_{x+i-1}^{i-1}$$$ for each $$$1 \leq i \leq n$$$ you can note, that when $$$i=1$$$ it is just $$$1$$$, and to get a value for $$$i+1$$$ you need multiply current value on $$$x+i-1$$$ and divide on $$$i$$$.
Then you can find scalar multiplication of these two vectors, and solve the task in $$$O(n \log^3{n}$$$).