小 S 现在拥有 座城市，第 座城市的人口为 ，城市与城市之间可能有双向道路相连。

现在小 S 要将这 座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。

假设小 S 将这些城市划分成了 个州，设 是第 个州包含的所有城市所组成的集合。定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 ），则称这个州是不合法的。

定义第 个州的满意度为：第 个州的人口在前 个州的人口中所占比例的 次幂，即：

定义一个划分的满意度为所有州的满意度的乘积。

求所有合法的划分方案的满意度之和。

答案对 取模。

两个划分 {V1…Vk} 和 {C1…Cs} 是不同的，当且仅当 ，或存在某个 ，使得 。