## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1937

# Curious Guardians

By Stefano Tommasini Brazil

Timelimit: 1

Oa is one of the ancient worlds of the DC universe, it is there that inhabit the guardians of the universe. They administer the Green Lantern Corps, a major force in the universe! Everyone knows that the Green Lanterns can fly because of the power of the ring, but not all the inhabitants of Oa are part of the troop. For these people is difficult getting between cities, as there are no roads!

The guardians want to connect the cities of Oa building some roads. There are N cities in Oa, and they want to build N-1 road of both hands, so that you can get from one city to any other directly or indirectly. The guardians also do not want too much focus any city, so they established that no city can have more than K roads. For example, if we have three cities and K equals 2, we have three options:

The guardians though, are very curious, and asked the Green Lanterns if they were able to tell how many ways you can build N-1 road obeying these restrictions. Your task, as a member of the Green Lantern Corps is N and K data, satisfy the curiosity of guardians.

## Input

The input consists of a single line containing two integers N (1 ≤ N ≤ 102) and K (1 ≤ KN).

## Output

Your program should produce a single line containing a single integer, the problem response. As this response may be very large, print it module of 109 + 7.

 Input Samples Output Samples 3 2 3

 4 1 0

 4 3 16

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

typedef long long ll;

ll dp[105][105];

ll comb[105][105];
int N;

void calc()
{
comb[0][0] = 0;
for (int i = 1; i  < = 101; ++i)
{
comb[i][0] = comb[0][i] = 1;
for (int j = 1; j  < = i; ++j)
{
comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
//	cout << "Comb[ " << i << " ] [ " << j << " ] = " << comb[i][j] << '\n';
}
}
}
ll solve(int n, int k)
{
if (k == 1)
if (n  < = 1) return 1;
else return 0;

if (n  < = 1) return 1;

ll &ans = dp[n][k];

if (ans == -1)
{
ans = 0;

for (int i = 1; i  < = n; ++i)
{
ans += comb[n - 1][i - 1] * i * solve(n - i, k - 1) * solve(i - 1, k - 1);
}
}
return ans;
}

int main()
{
ios_base :: sync_with_stdio(0); cin.tie(0);

calc();
int k;
cin >> N >> k;
memset(dp, -1, sizeof dp);

cout << solve(N - 1, k) << '\n';
}
``````
Copy The Code &

Input

cmd
3 2

Output

cmd
3