问题描述
一个自然数可以写成若干个小于等于自己的自然之和，
这叫该自然数的一个分解。
不同的分解是表示这个自然数分解成的所有自然数不完全相同。
例如：3=2+1和3=1+1+1表示不同的分解。而3=2+1和3=1+2为相同的分解。
现在的任务是，给出一个自然数，
要求所有不同的分解方案数 mod 19930125的值。

输入格式
一个自然数n。

输出格式
n的分解方案数mod 19930125的值（"mod"就是C++的"%"）。

样例输入
3

样例输出
2

提示
对于 60% 的数据： n<=2000
对于 100% 的数据： n<=5000