#P3321. 生成树Stcnt

    ID: 2509 传统题 1000ms 512MiB 尝试: 121 已通过: 35 难度: 7 上传者: 标签>CF2300提高+/省选-生成树计数Matrix-Tree 定理快速幂矩阵谱分解

生成树Stcnt

题目描述

给定两个数 n,kn,k,求出满足条件的树的个数:

  • 有 nknk 个点,标号为 0∼nk0\sim nk-11;

  • 如果 i≡j( mod  n)i\equiv j(\bmod\text{ }n),则 i,ji,j 间不存在边。

输入格式

  一行两个数 n,kn,k。

输出格式

一行一个数,表示答案模 109+710^9+7 的结果。  

2 2
4

数据规模与约定

对于 100%100\% 的数据,1≤n,k≤1091\leq n,k\leq 10^9。