Problem Description

Mingming is going on a trip again. Unlike last time, this time he is going on a space adventure. Let’s not talk about how “NC” he is. He is imagining what things he should bring. Of course, you need to help him calculate the number of ways to bring a total of $n$ items.

This time he plans to bring some popular foods, such as: Mi Tao Duo La, chicken nuggets, Chengde hamburgers, and so on.

Of course, he also has some strange restrictions:

The restrictions for each type of food are as follows:

• Chengde hamburger: an even number;
• Cola: $0$ or $1$;
• Chicken drumstick: $0$, $1$, or $2$;
• Mi Tao Duo: an odd number;
• Chicken nuggets: a multiple of $4$;
• Baozi: $0$, $1$, $2$, or $3$;
• Potato chips stir-fried with meat: at most one;
• Bread: a multiple of $3$.

Note that we will not consider how Mingming matches these foods when eating, and we also assume each type of food is counted in “pieces” (after all, it is just imagination). As long as the total number adds up to $n$, it counts as one valid plan. Therefore, for the given $n$, you need to compute the number of plans, and take it modulo $10007$.

Input Format

One integer $n$, representing the total count.

Output Format

One integer, representing the number of plans modulo $10007$.

1

1

5

35

Hint

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

Translated by ChatGPT 5