Bell

Time Limit: 3000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 4767
64-bit integer IO format: %I64d      Java class name: Main

Description

What? MMM is learning Combinatorics!?
Looks like she is playing with the bell sequence now:
bell[n] = number of ways to partition of the set {1, 2, 3, ..., n}

e.g. n = 3:
{1, 2, 3}
{1} {2 3}
{1, 2} {3}
{1, 3} {2}
{1} {2} {3}
so, bell[3] = 5

MMM wonders how to compute the bell sequence efficiently.

Input

T -- number of cases
for each case:
  n (1 <= n < 2^31)

Output

for each case:
  bell[n] % 95041567

Sample Input

6
1
2
3
4
5
6

Sample Output

1
2
5
15
52
203

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .