SP11947 GSWORDS - Counting Words

_Supervin likes counting. In this problem, he invites you to count together_ Supervin defines a **word** as "a string only consist of 'o' or 'x'", and additional requirement, for each substring with prime-length, the number of 'o' is not less than the number of 'x'. Supervin gives you an integer **N** (1

One line, an integer **N**

One line, an integer indicates how many **N**-length **words** modulo 1 000 000 007