Description

输入$n, m, k$,输出下面公式的值。
$\sum_{i=0}^{n}C{^i_n}*C{^m_n}*i^k$
其中$C{^m_n}$是组合数，表示在$n$个人的集合中选出$m$个人组成一个集合的方案数。组合数的计算公式如下：
$C{^m_n}=\frac{n\times (n-1)\times (n-2)\times...\times1}{[m\times(m-1)\times(m-2)\times...\times1]\times[(n-m)\times(n-m-1)\times...\times1]}$

对于100%的数据，$n$在十进制下不超过1000位，即$1≤n< 10^1000，1≤k≤1000$，同时$0≤m≤n，k≤n$。
提示: 999101是一个质数； 当$n$位数比较多时，绝大多数情况下答案都是0，但评测的时候会选取一些答案不是0的数据；

Format

Input

输入的第一行包含一个整数$n$；第二行包含一个整数$m$，第三行包含一个整数$k$。

Output

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

Samples

3
1
3

162