题目描述

​ 对一个正整数K，求出K的所有拆分，并统计输出其中回文数列的个数。所谓回文数列是指该数列中的所有数字，从左向右或从右向左看都相同。

例如，K=4时，有如下的拆分：

4=1+1+1+1

=1+1+2

=1+2+1

=2+1+1

=2+2

=1+3

=3+1

回文数列共有3个：1+1+1+1，1+2+1，2+2。

输入格式

​一行一个正整数K，1≤K≤26。

输出格式

一行一个正整数，所有拆分形成的回文数列个数。

样例数据

input

4

output

3

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$128 \text{MB}$