描述

把包含N个元素的集合{1,2,3…N}划分成若干个非空子集的方案数被称为贝尔数,记为Bell(N)。例如,当N=3时:
{1, 2, 3}
{1} {2 3}
{1, 2} {3}
{1, 3} {2}
{1} {2} {3}
有以上五种划分方案,因此Bell(3)=5。
现在MHC想知道如何快速地计算贝尔数。如果Ta给你一个正整数N,你能告诉Ta Bell(N) mod 95041567的值吗?

输入格式

第一行一个正整数T,表示数据组数。
接下来T行,每行一个正整数N,表示要计算Bell(N)。

输出格式

一共T行,每行一个整数,表示Bell(N) mod 95041567的值。

样例输入

6
1
2
3
4
5
6

样例输出

1
2
5
15
52
203

数据范围与约定

  • 对于50%的数据,1<=N<=1000。
  • 对于100%的数据,1<=N<=2147483647,1<=T<=10,保证不会十组都是大数据。

提示

你可能会用到以下公式:
(1) 贝尔数递推公式:
Bell_{n+1}=\sum_{k=0}^{n}C_{n}^{k}*Bell_{k}

(2) Touchard同余公式:若p是任意质数,则:

Bell_{n+p}\equiv Bell_{n}+Bell_{n+1} (mod\ p)