Unimodal Palindromic Decompositions

Time limit1sMemory limit128 MB

Summary

Count the number of ways to write N as a sum of a palindromic sequence whose values rise to the middle then fall.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

A sequence of positive integers is palindromic if it reads the same forwards and backwards. For example:

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

A palindromic sequence is unimodal palindromic if the values are non-decreasing up to the middle value and then (because the sequence is palindromic) non-increasing from the middle to the end. For instance, the first sequence above is not unimodal palindromic, while the second one is.

A unimodal palindromic sequence is a unimodal palindromic decomposition of an integer $N$ if the integers in the sequence sum to $N$ . For example, the unimodal palindromic decompositions of the first few integers are:

(1)
(2), (1 1)
(3), (1 1 1)
(4), (1 2 1), (2 2), (1 1 1 1)
(5), (1 3 1), (1 1 1 1 1)
(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), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)
(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)

Given an integer $N$ , compute the number of its unimodal palindromic decompositions.

Input

The input consists of a sequence of positive integers, one per line. A line containing a single 0 marks the end of the input and is not processed.

Output

For each input value except the terminating 0, print one line containing the value, a single space, and the number of unimodal palindromic decompositions of that value.

Constraints

$1 \le N \le 250$

Examples3

Example 1

Input

Expected output

2 2
3 2
4 4
5 3
6 7
7 5
8 11
10 17
23 104
24 199
131 5010688
213 1055852590
92 331143

Example 2
Input
```
1
0
```
Expected output
```
1 1
```
Example 3
Input
```
1
2
3
0
```
Expected output
```
1 1
2 2
3 2
```