题目描述

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

例如K=4时，共有以下7种拆分：

1+1+1+1（回文数列 1）

1+1+2

1+2+1（回文数列 2）

2+1+1

2+2（回文数列 3）

1+3

3+1

其中有3种是回文数列。

输入格式

一个正整数K(K<26)。

输出格式

一个整数，表示K的所有拆分中回文数列的个数。

输入/输出样例

4

3

说明/提示

时间1000ms，内存256MiB