题目描述

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

4=1+1+1+1 {回文数列1}

4=1+1+2

4=1+2+1 {回文数列2}

4=2+1+1

4=2+2 {回文数列3}

4=1+3

4=3+1

回文数列共有3个。

输入格式

一个正整数K（ 1< K ≤ 26 ）。

输出格式

满足条件的回文数列的个数。

样例数据

input

4

output

3