Pascal's triangle is a geometric arrangement of sums that have interesting mathematical properties -- most famously, the binomial coefficients.

The rows of Pascal's triangle are conventionally enumerated starting with row 0, and the numbers in each row are usually staggered relative to the numbers in the adjacent rows.

A simple construction of the triangle proceeds in the following manner.

On row 0, write only the number 1.

Then, to construct the elements of following rows, add the number directly above and to the left with the number directly above and to the right to find the new value.

If either the number to the right or left is not present, substitute a 0 in its place.

For example, the first number in row 1 is 0 + 1 = 1, whereas the numbers 1 and 3 in row 3 are added to produce the number 4 in row 4. Here are the first six rows of Pascal's triangle.

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 

In the file problem3.py, write a program that prompts the user for the height of Pascal's triangle and then prints out the triangle in the same style as in the previous example. Height 1 would print a triangle containing a single row.

Hint: Use a list for each row, and use a list of lists to hold the whole triangle. Think about how the position of each number in the triangle can be translated to indices in the lists. There are many ways to solve this problem, but one is to keep placeholders in the list to represent "empty" cells in each row. Only every second entry would actually contain a number. This makes it easy to find the left and right parent of each cell.

Once the triangle includes three-digit numbers or longer, the alignment will become broken. This is okay, as long as the output of each line is centered.