Space Adventure Packing Problem

Mingming is about to embark on a universe exploration trip and, as usual, he wants to pack some of his favorite foods. However, each food has a peculiar constraint on the quantity that can be taken. Given an integer n representing the total number of food items to pack, you are to count the number of packing schemes modulo 10007 under the following restrictions (each number represents the number of items for that food):

• Chengde Hamburger: must be an even number (0, 2, 4, ...).
• Cola: can be either 0 or 1.
• Chicken Leg: can be 0, 1, or 2.
• Peach Dora: must be an odd number (1, 3, 5, ...).
• Chicken Nuggets: must be a multiple of 4 (0, 4, 8, ...).
• Baozi: can be 0, 1, 2, or 3.
• Fried Pork with Potato Chips: at most 1 (0 or 1).
• Bread: must be a multiple of 3 (0, 3, 6, ...).

Note that all items are counted in units and the order in which the items are chosen does not matter. In other words, a valid packing scheme is one selection of nonnegative integers a, b, c, d, e, f, g, h (one for each food in the order given above) satisfying
\(a + b + c + d + e + f + g + h = n\)
and the above conditions. Output the number of valid schemes modulo 10007.

inputFormat

The input consists of a single integer n (0 ≤ n ≤ some upper bound) on a single line representing the total number of items to be packed.

outputFormat

Output a single integer, the number of packing schemes modulo 10007.

sample

0

0