Problem 2820 - How many different ways| TJU ACM-ICPC Online Judge

2820. How many different ways

Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 288 Accepted Runs: 160

There is an easy math problem for you. Given you a positive integer K, indicating K different balls. The problem is to find out how many different ways to distribute all of the balls into some boxes (Of course, the box cannot be empty and all of the boxes are same). For example, if K = 3, so there are five different ways to distribute the balls:

{{1},{2},{3}},
{{1,2},{3}},
{{1,3},{2}},
{{2,3},{1}},
{{1,2,3}}

('1','2','3' indicate three different balls)

Input

The input will contain one or more test cases, one per line. Each test case contains a positive integer N. If N = 0 it signals the end of the input and isn't considered to be processed; otherwise, N will be a positive integer not more than 2000.

Output

For each test case, output a single line containing the number of different ways. Considering the answer may be very large, you should output the last four digits of the answer.

Sample Input

1 2 3 4 0

Sample Output

0001 0002 0005 0015

Problem Setter: mmatch@TJU

Source: TJU Programming Contest 2007

Submit List Runs Forum Statistics

Tianjin University Online Judge v1.2.4