小 S 现在拥有 nnn 座城市，第 iii 座城市的人口为 wiw_iwi，城市与城市之间可能有双向道路相连。
现在小 S 要将这 nnn 座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。
假设小 S 将这些城市划分成了 kkk 个州，设 ViV_iVi 是第 iii 个州包含的所有城市所组成的集合。定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 000），则称这个州是不合法的。
定义第 iii 个州的满意度为：第 iii 个州的人口在前 iii 个州的人口中所占比例的 ppp 次幂，即：
(∑x∈Viwx∑j=1i∑x∈Vjwx)p\left( \frac {\sum_{x \in V_i} w_x} {\sum_{j=1}^i \sum_{x \in V_j} w_x} \right)^p(∑j=1i∑x∈Vjwx∑x∈Viwx)p定义一个划分的满意度为所有州的满意度的乘积。
求所有合法的划分方案的满意度之和。
答案对 998244353998244353998244353 取模。
两个划分 {V1…Vk} 和 {C1…Cs} 是不同的，当且仅当 k≠sk \neq sk≠s，或存在某个 1≤i≤k1 \leq i \leq k1≤i≤k，使得 Vi≠CiV_i \neq C_iVi≠Ci。