题目描述

输入 n,m,k，输出下图所示的公式的值。

$\sum_{i=0}^{n}(C_{n}^{i} \times C_{n}^{m} \times i^k)$

其中 $C_{n}^{m}$ 是组合数，表示在 n 个人的集合中选出 m 个人组成一个集合的方案数。

组合数的计算公式如下图所示。

$C_{n}^{m}=\frac{n×(n−1)×(n−2)×⋯×1}{[m×(m−1)×⋯×1]⋅[(n−m)×(n−m−1)×⋯×1]}$

输入描述

输入的第一行包含一个整数 n；

第二行包含一个整数 m；

第三行包含一个整数 k。

其中，n 在十进制下不超过 1000 位，即 1≤n<10¹⁰⁰⁰，1≤k≤1000，同时 0≤m≤n，k≤n。

输出描述

计算题目中公式的值，由于答案非常大，请输出这个值除以 999101 的余数。

输入输出样例

示例

输入

3
1
3

输出

162