Bell
Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
System Crawler (2015-03-15)
System Crawler (2015-03-15)
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}
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)
for each case:
n (1 <= n < 2^31)
Output
for each case:
bell[n] % 95041567
bell[n] % 95041567
Sample Input
6
1
2
3
4
5
6
Sample Output
1
2
5
15
52
203