Partition Counting

You are given a non-negative integer ( n ). Your task is to compute the number of ways to express ( n ) as a sum of positive integers, where the order of the summands does not matter. This number is known as the partition number ( p(n) ).

The standard dynamic programming approach works as follows:

• Initialize an array \( dp[0 \ldots n] \) with \( dp[0] = 1 \) (there is exactly one way to partition 0) and \( dp[i] = 0 \) for \( i \ge 1 \).
• For each integer \( i \) from 1 to \( n \), iterate over \( j \) from \( i \) to \( n \) and update \( dp[j] = dp[j] + dp[j-i] \).

In the end, \( dp[n] \) will be the desired answer. For example, when \( n = 4 \), there are 5 partitions: \( 4, 3+1, 2+2, 2+1+1, 1+1+1+1 \).

inputFormat

The input consists of a single non-negative integer ( n ) (( 0 \le n \le 1000 )). Input is provided via standard input (stdin).

outputFormat

Output a single integer representing the number of partitions of ( n ) (i.e. the value of ( p(n) )). The output should be written to standard output (stdout).## sample

4

5