Description

As described in Wikipedia,
Bell triangle is a triangle of numbers analogous to Pascal's triangle, whose values count partitions of a set in which a given element is the largest singleton.

Construction of the Bell triangle:

Bell(1,1) = 1
Bell(n,1) = Bell(n-1,n-1), for n = 2, 3, 4, ...
Bell(n,k) = Bell(n-1,k-1) + Bell(n,k-1), for n = 2, 3, ... and k = 2, 3, ...

Or you can do step by step as follow:

Given a postive integer N,
display the Bell’s triangle from row 1 to row N.
Use '%11d' to print each row element and print a newline at the end of each row.

Input

Given a postive number N and the range of N is 1 ≦ N ≦ 15.

Output

Print the Bell triangle from row 1 to row N,
and all elements of Bell triangle are smaller than 2³¹-1.

Sample Input  Download

Sample Output  Download

Tags

Discuss