#P18617. Directed Vertex Cacti

Directed Vertex Cacti

Directed Vertex Cacti

给定两个整数 n,mn,m。

求满足以下全部条件的有向图 GG 的数量:

  • 恰有 nn 个顶点,标号为 1,…,n1,\ldots,n;
  • 没有自环,也没有同向重边;
  • 每个顶点至多属于一个简单有向环;
  • 恰有 mm 条边不属于任何有向环。

如果存在标号为 u,vu,v 的顶点,使得有向边 u→vu\to v 只在两个图中的一个里存在,则这两个图不同。

简单有向环指沿边方向行走、除首尾重合外不重复经过顶点的环。

输入格式

仅一行,两个整数 n,mn,m(1≤n,m≤1061\le n,m\le10^6)。

输出格式

输出满足条件的图的数量对 109+910^9+9 取模的结果。

样例输入 1

3 1

样例输出 1

18

样例输入 2

4 4

样例输出 2

360

样例输入 3

39847 348708

样例输出 3

983575456

说明

“没有重边”是指不能存在两条不同的 u→vu\to v 边。但可以同时存在 u→vu\to v 和 v→uv\to u,这两条边构成长度为 22 的简单有向环。

mm 只统计不属于任何环的边,图的总边数可以大于 mm。不要求图连通。