양의 정수의 수열이 주어질 때 앞으로 읽던 뒤로 읽던 같은 수열이면 회귀적(palindromic)이라고 한다.

예를 들어 두 수열은 회귀적이다.

23 11 15 1 37 37 1 15 11 23 
1 1 2 3 4 7 7 10 7 7 4 3 2 1 1 

23 11 15 1 37 37 1 15 11 23  -- not unimodal palindromic 
1 1 2 3 4 7 7 10 7 7 4 3 2 1 1 -- unimodal palindomic 

문제는 양의 정수 N 이 주어질 때 수열이 합의 N 이 되는 unimodal palindomic 이 되는 수열의 개수를 출력하는 것이다.

몇가지 보기를 들면,

1: (1)  -- 한 개 
2: (2), (1 1)  -- 두 개
3: (3), (1 1 1)  -- 두 개 
4: (4), (1 2 1), (2 2), (1 1 1 1) -- 네 개
5: (5), (1 3 1), (1 1 1 1 1) 
6: (6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3), (1 2 2 1), ( 1 1 1 1 1 1) 
7: (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1) 
8: (8), (1 6 1), (2 4 2), (1 1 4 1 1), (1 2 2 2 1), (1 1 1 2 1 1 1), ( 4 4), (1 3 3 1), (2 2 2 2), (1 1 2 2 1 1), (1 1 1 1 1 1 1 1) 

입력

출력

입출력 예

입력

2

출력

2

입력

8

출력

11

출처:Greater New York 2002