A partition of an integer is a series of numbers that add up to . For example, given the number 15, an partition could be , which adds up to 15. A palindromic partition is when that series of numbers is a palindrome. For example, a palindromic partition of the number 15 can be .

To be specific, a palindrome series of numbers count the numbers as individual characters, so the palindromic series `10 + 1 + 10`

will work if the number is , and just `21`

will also work for the same case (shown in sample).

Given a number , please find the number of different palindromic partitions.

**Note**: For partitions, the numbers must be **POSITIVE INTEGERS**.

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [50%]

##### Subtask 3 [20%]

#### Input Specification

One integer .

#### Output Specification

One integer , the number of different palindromic partitions.

#### Sample Input

`7`

#### Sample Output

`8`

#### Explanation of Sample

The palindromic partitions of are:

```
7 = 7
7 = 1 + 5 + 1
7 = 2 + 3 + 2
7 = 3 + 1 + 3
7 = 1 + 1 + 3 + 1 + 1
7 = 2 + 1 + 1 + 1 + 2
7 = 1 + 2 + 1 + 2 + 1
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1
```

In total, there are 8 palindromic partitions.

## Comments