The pascal triangle is formed by natural numbers in several lines: First line is "1" and second "1 1". Each following line starts and ends with 1 and inside numbers are the sum of the two numbers above. The pascal triangle starts like this:

       1
      1 1
     1 2 1
    1 3 3 1
    ...

Your program should ignore input. In the standard output it should print all the subsequent lines of the pascal triangle until one number greater than 1000000 will be encountered. The associated line should NOT be printed. No leading or trailing spaces. One space between each number. No empty or spanning lines.