Xâu đối xứng kép

Một xâu được gọi là đối xứng kép nếu nó có thể tách làm hai xâu đối xứng (một trong hai xâu đó có thể rỗng). Nói cách khác, xâu đối xứng kép là xâu đối xứng hoặc được ghép từ hai xâu đối xứng. Ví dụ xâu \(banana\), \(abcba\) là các xâu đối xứng kép. Hãy đếm số xâu đối xứng kép độ dài không quá \(n\), chỉ chứa các ký tự latin thường.

Input

Dòng duy nhất chứa số nguyên dương \(n\)

Output

Ghi kết qủa sau khi chia lấy dư cho \(10^9 + 7\)

Example

2

702

3

2678

4

38454

Scoring

• \(1 ≤ n ≤ 10^5\)

• \(20\%\) test có \(n ≤ 15\)

• \(20\%\) test có \(n ≤ 1000\)