TopCoder problem "SuperSum" used in SRM 467 (Division I Level Two)



Problem Statement

    SuperSum is a function defined as:

  • SuperSum(0 , n) = n, for all positive n.
  • SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n.

Given k and n, return the value for SuperSum(k , n) modulo 1000000007.

 

Definition

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

Constraints

-k will be between 1 and 50, inclusive.
-n will be between 1 and 1000000000, inclusive.
 

Examples

0)
    
1
3
Returns: 6
When k = 1, SuperSum is equal to the sum of the first n = 3 numbers: 1 + 2 + 3 = 6.
1)
    
2
3
Returns: 10
SuperSum(2 , 3) = SuperSum(1 , 1) + SuperSum(1 , 2) + SuperSum(1 , 3) = 1 + 3 + 6 = 10.
2)
    
4
10
Returns: 2002
3)
    
10
35
Returns: 150595840

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10239

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14151&pm=10239

Writer:

vexorian

Testers:

PabloGilberto , misof , ivan_metelsky

Problem categories:

Advanced Math