Problem Description

Mingming is going on a space adventure this time, unlike his previous travel. For now, he is fantasizing about what he should bring. Naturally, you are tasked with calculating the number of ways to carry $n$ items.

He plans to bring some popular foods, such as Peach Duo, Chicken Nuggets, Chengde Burgers, etc.

Of course, he has some peculiar restrictions:

The restrictions for each food item are as follows:
- Chengde Burger: Even number of pieces;
- Cola: $0$ or $1$ can;
- Chicken Leg: $0$, $1$, or $2$ pieces;
- Peach Duo: Odd number of pieces;
- Chicken Nuggets: Multiple of $4$ pieces;
- Buns: $0$, $1$, $2$, or $3$ pieces;
- Potato Slices with Meat: No more than one serving;
- Bread: Multiple of $3$ pieces;

Note that we are not considering how Mingming should mix and match the foods, and we assume each food item is counted by 'pieces' (after all, it's a fantasy). As long as the total number adds up to $n$, it counts as one scheme. Therefore, for a given $n$, you need to calculate the number of schemes and take the result modulo $10007$.

Input Format

A single integer $n$, representing the total number.

Output Format

A single integer, representing the number of schemes modulo $10007$.

Sample Input and Output

Sample Input #1

1

Sample Output #1

1

Sample Input #2

5

Sample Output #2

35

Notes

• For $40\%$ of the data, $1 \leq n \leq 10^5$;
• For all data, $1 \leq n \leq 10^{500}$;

见题面 Input 部分

见题面 Output 部分