Butch unfortunately missed the most recent LSU football game, but he was luckily able to get the score S (0 ≤ S ≤ 30) from a friend. So he got to thinking, how many possible ways could LSU have scored this?

Remember that the ways to score are like so:

2 - Safety
3 - Field Goal
6 - Touchdown with missed extra point or failed conversion (only include one 6-point in your calculations; see note below)
7 - Touchdown with the extra point
8 - Touchdown with a 2 point conversion

Butch would figure out how many ways himself, but he's busy scouring the web for a replay, so he wants you to help.

Note: The order is important. For example, if the input is 5, there would be 2 ways: LSU could score a safety and then a field goal, or it could score a field goal and then a safety.

Note about the 6 point-ers: For example 8 points in total, the number of ways to score would be:

2-2-2-2

2-3-3

3-2-3

3-3-2

2-6

6-2

8

See that there is only one set of "6-2" and "2-6"; in other words, we don't say "they scored from a safety and they scored from a touchdown with a failed extra point" and "they scored from a safety and they scored from a touchdown with a failed conversion", etc... From Neal, "You should not consider scoring the touchdown and missing the extra point, and scoring the touchdown and failing the conversion as two separate ways to score."

Another note: Values may not be precalculated and stored in an array. Any solution that does this will be disqualified and receive 0 points.

Extra Challenge: The last test case will have S ≤ 10000.

Find the number of ways that a score S can be made in a football game, modulo 10000.

Input

Line 1: A single integer, S

Output

Line 1: A single integer, how many ways they could score

Example

Input:
8

Output:
7