Palindromic Sum Decomposition

Professor H, an expert in cryptography, has devised a novel method called the Palindromic Sum Decomposition for decomposing a positive integer (n) into a sum of positive integers (x_1, x_2, \ldots, x_k) satisfying (n=x_1+x_2+\cdots+x_k) such that the sequence (x_1, x_2, \ldots, x_k) reads the same from left to right and right to left. Two decompositions are considered different if they have a different number of summands or the sequences differ at some position.

For example, for (n=6) there are 8 palindromic sum decompositions:

• \(6\)
• \(2+2+2\)
• \(3+3\)
• \(2+1+1+2\)
• \(1+4+1\)
• \(1+1+2+1+1\)
• \(1+2+2+1\)
• \(1+1+1+1+1+1\)

Given a positive integer (n), count the number of distinct palindromic sum decompositions modulo (10^9+7).

inputFormat

The input consists of a single positive integer (n) (1 (\leq n \leq) large).

outputFormat

Output a single integer, the number of palindromic sum decompositions of (n) modulo (10^9+7).

sample

6

8