#P3456. 城市规划

    ID: 2656 传统题 1000ms 512MiB 尝试: 1649 已通过: 452 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划计数 DP组合数学补集计数阶乘逆元预处理多项式与生成函数卷积转化离线与分治CDQ 分治NTTCF2400

城市规划

城市规划

题目描述

阿狸的国家有 nn 个城市,编号为 11 到 nn。国家要在一些不同的城市对之间修建双向贸易路线,使得任意两个城市都可以通过一条或多条路线相互到达。每对城市之间至多修建一条直接路线。

如果有一对城市在两个方案中是否直接相连的情况不同,这两个方案就是不同的。求可行方案的数量,也就是 nn 个带编号顶点的无向简单连通图的数量,对 1004535809=479×221+11004535809=479\times 2^{21}+1 取模。

输入格式

输入一行一个整数 nn,1≤n≤1300001\le n\le 130000。

输出格式

输出一行一个整数,表示方案数取模后的值。

样例 #1

3
4