1713: 记忆化递归-母牛生小牛问题
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 137 Solved: 73
[Status] [Submit] [Creator:]
Description
有一头母牛，每年年初生一只小牛，每头小牛从第4个年头开始，每年年初也生一头母牛。
（出生的那年算第一个年头，也就是说对于小牛来说，第4个年头它刚好3周岁）
求：到第 n 年的时候，共有多少头母牛。
由于数据量可能很大，所以你只需要输出母牛数量除以 1000 的余数即可。
（出生的那年算第一个年头，也就是说对于小牛来说，第4个年头它刚好3周岁）
求：到第 n 年的时候，共有多少头母牛。
由于数据量可能很大，所以你只需要输出母牛数量除以 1000 的余数即可。
Input
一个整数 n（1 ≤ n ≤ 1000）。
Output
输出一个整数，表示第 n 年的时候母牛的数量除以 1000 的余数。
Sample Input Copy
【样例输入1】
1
【样例输出1】
2
【样例输入2】
5
【样例输出2】
9
【样例输入3】
10
【样例输出3】
60
HINT
【样例解释】
