JOIN
Get Time

   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