## Description

We define a tree valid if and only if on each node there is a number in $S$, and the value of this true is define as the sum of these numbers.

Given $n,m,S$, for each $k$ in $[1,m]$ find out the number of valid **binary** trees with $n$ nodes and value $k$.

## Tutorial

Define the OGF to the answer as $F$, and $G(x) = \sum_{k=0}^\infty [k \in S]x^k$.

We know that a binary tree is defined as follow:

- An empty tree is a binary tree
- The combination of a root and two son binary trees(with order)

The there is clear that

So

As is obviously that

We know the $\pm$ should be $+$

## Code

```
#include "~/code/Math/Poly/main.h"
void solve()
{
using namespace Polys;
int n = sc.n(), m = sc.n();
Poly A(m+1);
rep (i,n) {
int u = sc.n();
if (u <= m) A[u] -= 4; }
A[0] = 1;
A = A.sqrt();
A[0] = 2;
A = A.inv();
A *= Int(2);
repa (i,m) printf("%u\n", static_cast<unsigned>(A[i]));
}
```