本题满分 。
在遥远的 Airlanvaosma-i 国度，有 座城市，由 条道路连接，且从任意城市到任意城市都能到达。并且任意两座城市之间的最短路经过的道路数都小于 。
Krešimir 想建立自己的国家。一个国家必须选择：
- 个首都（从这里治理国家）；
- 若干个（可以为 个）次级城市（归首都管辖）。
国家的规模定义为该国家包含的城市总数（包含首都和所有次级城市）。
为了保证治理效率，Krešimir 规定：
- 对每一个次级城市，在从首都到该次级城市的路径上，不能出现其他次级城市。
换句话说：不允许某个次级城市位于首都与另一个次级城市之间。
对每个规模 （），求 Krešimir 能建立多少个不同规模为 的国家。答案可能很大，请输出它对 取模的结果。
定义两个国家建立方案不同，当且仅当两个国家在“首都选择”或“任一被选为次级城市的城市”上有不同。
