JOIN

 Problem Statement

Problem Statement for CrazyFunctions

### Problem Statement

In this problem, a function is any function that maps integers from 1 to n to integers from 1 to n. For example, if n=3, one possible function is the function g defined as follows: g(1)=1, g(2)=3, and g(3)=1.

We will use the notation f^(j)(x) to denote applying a function f to the input x exactly j times in a row. Formally:

• for all valid x, f^(0)(x) = x
• for all valid x and j, f^(j+1)(x) = f^(j)(f(x))

We will now formally define several new notations.

• G(f,w) will be the set of all values f^(r)(x), where x is between 1 and n, inclusive, and r is greater than or equal to w.
• S(f,w) will be the size of G(f,w).
• Z(f) will be the minimum of S(f,w), taken over all nonnegative w.
• A(y) will be the set of all functions f such that Z(f) = y.

You are given the int n and an int k. Compute and return the size of the set A(k), modulo 1,000,000,007.

### Definition

 Class: CrazyFunctions Method: count Parameters: int, int Returns: int Method signature: int count(int n, int k) (be sure your method is public)

### Constraints

-n will be between 1 and 5,000, inclusive.
-k will be between 1 and n, inclusive.

### Examples

0)

 `2` `1`
`Returns: 2`
 We have n = 2, which means that there are four different functions. Let's call them a, b, c, d as follows: a(1) = 1 and a(2) = 1 b(1) = 1 and b(2) = 2 c(1) = 2 and c(2) = 1 d(1) = 2 and d(2) = 2 Two of these functions (functions a and d) belong into the set A(1), so the correct return value is 2. The other two functions (b and c) belong into the set A(2).
1)

 `2` `2`
`Returns: 2`
2)

 `1` `1`
`Returns: 1`
3)

 `3` `1`
`Returns: 9`
4)

 `3` `3`
`Returns: 6`
5)

 `5` `3`
`Returns: 900`
6)

 `5000` `5000`
`Returns: 541108809`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 700 Sponsored by Booz Allen Ham Round 1 - Division I, Level Two