Description

将一个数字n拆分成单调递减回文串，有多少种方式？这里的单调递减，指的是从对称轴处向左向右的数字均为单调不上升的，在这里举一些例子： 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)

Format

Input

一个数字n(n <= 250 )

Output

一个整数，表示将一个数字n拆分成单调递减回文串的方案数

Samples

8

11

213 

1055852590

Limitation

1s, 1024KiB for each test case.