同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21833_Countingspanningtrees

2022-5-16 18:20| 发布者: Hocassian| 查看: 25| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505886971000-Problem List-采集的数据-后羿采集器.html

Pro.ID

21833

Title

Counting spanning trees

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21833

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

Everyone knows spanning trees, especially MST problem. But most of them are not familiar with degree constrained spanning tree.

a degree-constrained spanning tree is a spanning tree which the maximum vertex degree is limited to a certain constant d.

Given two integers n and d, your task is to count the number of degree constrained spanning trees of a (labeled) complete graph with n vertices.

输入

Each line contains two integers n, d. 1 ≤ n ≤ 100 , 1 ≤ d ≤ 100.

输出

Description

Everyone knows spanning trees, especially MST problem. But most of them are not familiar with degree constrained spanning tree.

a degree-constrained spanning tree is a spanning tree which the maximum vertex degree is limited to a certain constant d.

Given two integers n and d, your task is to count the number of degree constrained spanning trees of a (labeled) complete graph with n vertices.

Input

Each line contains two integers n, d. 1 ≤ n ≤ 100 , 1 ≤ d ≤ 100.

Output

For each query, output a line which contains only one integer, the number of degree constrained spanning trees of a (labeled) complete graph with n vertices. This number may be very large, so output the answer modulo 20090829.

Sample Input

3 1
3 2
4 2
10 3

Sample Output

0
3
12
3458313

Source

2009 Multi-University Training 17

样例输入