Count the Number of Partitions of n

In the Treasury of Prime City, the Treasurer must count the number of ways to partition an integer n into positive integers that sum to n. The order of parts does not matter. For example, p(4) = 5: {4}, {3+1}, {2+2}, {2+1+1}, {1+1+1+1}. "Use the generating function approach or dynamic programming," the Treasurer says. "The DP approach: dp[i][j] = number of partitions of i using parts no larger than j. dp[i][j] = dp[i][j-1] + dp[i-j][j] (if i >= j)." Given n, compute p(n) ÔÇö the number of integer partitions of n, modulo 10^9 + 7. Constraints: 0 <= n <= 5000 Input: 4 Output: 5 Input: 5 Output: 7