公式求值 ### 题目描述 输入 $n, m, k$，输出下图所示的公式的值。 $\sum_{i=0}^{n}(\dbinom{i}{n} \cdot \dbinom{m}{n} \cdot i^{k} )$ 其中 $\dbinom{m}{n}$ 是组合数，表示在 n 个人的集合中选出 m 个人组成一个集合的方案数。 组合数的计算公式如下图所示。 $\dbinom{m}{n}=\frac{n \times (n-1) \times (n-2) \times \cdots \times 1 }{[m \times (m-1) \times \cdots \times 1] \cdot [(n-m) \times (n-m-1) \times \cdots \times 1] }$ ### 输入描述 输入的第一行包含一个整数 $n$； 第二行包含一个整数 $m$； 第三行包含一个整数 $k$。 其中，$n$ 在十进制下不超过 1000 位，即 $1 \leq n<10^{1000}，1 \leq k \leq 1000$，同时 $0 \leq m \leq n，k \leq n$。 ### 输出描述 计算题目中公式的值，由于答案非常大，请输出这个值除以 999101 的余数。 ### 输入输出样例 #### 示例 > 输入 ```txt 3 1 3 ``` > 输出 ```txt 162 ```