Modified Pascal's Triangle with Fibonacci Numbers

You are given an integer \(T\) representing the number of test cases. For each test case, a single integer \(n\) is provided which indicates the number of rows to generate in Pascal’s triangle.

First, generate the standard Pascal’s triangle with \(n\) rows. Then, for each entry \(x\) in the triangle, compute the Fibonacci number \(F(x)\) modulo \(10^9+9\), where the Fibonacci sequence is defined as follows:

[ F(0)=0,\quad F(1)=1,\quad F(n)=F(n-1)+F(n-2)\quad (n\ge2). ]

Replace each entry in the triangle with its corresponding Fibonacci number. Finally, output the modified triangles for all test cases consecutively. Within each triangle, each row is printed on a new line and the numbers in a row are separated by a single space.

inputFormat

The first line of input contains a single integer \(T\) representing the number of test cases. This is followed by \(T\) lines, each containing one integer \(n\), the number of rows for that test case’s Pascal’s triangle.

outputFormat

For each test case, print the modified Pascal’s triangle where each entry is replaced by its Fibonacci number modulo \(10^9+9\). Each row should be on a new line and numbers within the same row should be separated by a single space. The triangles for consecutive test cases are printed one after another with no blank lines in between.

1
1

1