Migrated from Lutece 420 lili‘s number

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Once upon a time,there's a boy whose name is lili.He likes to create many wonderful things.One day, he happens to come to a beautiful garden.There he picks many pretty little stones.Again,his heart tells him that he should use them to create some incredible things!So he decides to put them in a line of boxes,each box has at most one stone,just as the road which he used to walk on in his childhood.But again,he wants to make his works different.So he wants no two adjacent boxes to have stones both.He wonders how many ways that stones be put into boxes.Can you help him to finish his great work?

Input

multiple cases:

• $n$($0\leq n\leq 100000$)the number of the boxes

Output

The number described above MOD $10007$.

Samples

0
1

1
2

Resources

5th BUPT Programming Contest Preliminary