Counting Colored Trees with Bounded Maximum Independent Set

A tree \(T=(V,E)\) is an undirected, connected, and acyclic simple graph. In this problem, we consider trees on \(n\) vertices whose vertices are each assigned one of \(c\) colors. Two colored trees \(T_1=(V_1,E_1)\) and \(T_2=(V_2,E_2)\) are considered equal if and only if:

• There exists a bijection \(\pi:V_1\to V_2\) such that for any two vertices \(u,v \in V_1\), \(\{u,v\}\in E_1\) if and only if \(\{\pi(u),\pi(v)\}\in E_2\).
• For every vertex \(v \in V_1\), the color of \(v\) in \(T_1\) is the same as the color of \(\pi(v)\) in \(T_2\).

An independent set of a tree is a subset \(S\subseteq V\) such that no two distinct vertices in \(S\) are adjacent. Its size is the number of vertices in \(S\), and the maximum independent set size of \(T\) is the largest size among all independent sets of \(T\>.

Your task is: Given four integers \(n, l, r, c\), count the number of distinct c-colored trees on \(n\) vertices whose maximum independent set size lies in the interval \([l, r]\). Since this number may be very large, output it modulo \(998244353\).

Note: Two colored trees are considered the same if there is a color‐preserving isomorphism between them. In our input, \(n\) (the number of vertices) is small (for example, \(n\le 7\)) so that a brute‐force solution is feasible.

inputFormat

The input consists of four space‐separated integers:

1. \(n\) — the number of vertices in the tree.
2. \(l\) — the lower bound for the maximum independent set size.
3. \(r\) — the upper bound for the maximum independent set size.
4. \(c\) — the number of available colors (each vertex is colored with an integer from \(1\) to \(c\)).

outputFormat

Output a single integer: the number of distinct c-colored trees on \(n\) vertices whose maximum independent set size is in the interval \([l, r]\), taken modulo \(998244353\).

sample

3 1 2 2

3