T2 组合数问题

题目信息

时间限制: 1.5s

空间限制: 512M

输入文件: fc.in

输出文件: fc.out

题目描述

组合数 $\binom{n}{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $\binom{n}{m}$ 的一般公式：

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

其中 $n!=1\times2\times\cdots\times n$；特别地，定义 $0!=1$。

看到这里，你可能会想到，某年NOIP不是也有道组合数问题吗，题目描述甚至还很像！？

可惜两道题有亿点点区别。

我们利用组合数定义一下$f(n,k)$，他等于：

$$\sum_{x_1=0}^n \binom{n}{x_1} \sum_{x_2=0}^{x_1} \binom{x_1}{x_2} \sum_{x_3=0}^{x_2} \binom{x_2}{x_3} \dots \sum_{x_k=0}^{x_{k-1}} \binom{x_{k-1}}{x_k} $$

特别地，规定 $f(n,0)=1$。

然后麻烦你求解：

$$\sum_{i=0}^n f(f(n,i),i) \mod 998244853$$

输入格式

本题含有多组数据

第一行为一个整数 $T$，表示数据组数。

对于每组数据，一行一个整数，表示 $n$。

输出格式

对于每组数据，一行一个整数，表示答案。

样例

输入1

3
1
10
100

输出1

5
909927378
208415843

数据范围与提示

对于所有的测试点, $T \le 5, n \le 2 \times 10^5$。

• 对于 $20 \%$ 的数据, 满足 $n \le 10$
• 对于 $60\%$ 的数据, 满足 $n \le 10^3$
• 对于 $100 \%$ 的数据, 满足 $n \le 2 \times 10^5$