static int[][] PasTri(int n){
    int[][] res = new int[n][];
    res[0] = new int[1] {1};
    res[1] = new int[2] {1, 1};
    for(int i=2; i< n; i++){
        res[i]= new int[i+1];
        res[i][0]=1;
        for(int j=1; j< i; j++) res[i][j]=res[i-1][j-1]+res[i-1][j];
        res[i][i]=1;
    }
    return res;
}

 static int[][] PasTri(int n){
    int[][] trykutnyk = new int[n][];
    for(int i=0; i< n; i++){
        trykutnyk[i] = new int[i+1];
        trykutnyk[i][0] = 1;
        for(int j=1; j<=i; j++){
            trykutnyk[i][j] = trykutnyk[i-1][j-1] + (j< i ? trykutnyk[i-1][j] : 0);
        }
    }
    return trykutnyk;
}

 static int[][] PasTri(int n)
        {
            int[][] arr = new int[n][];
            for (int i = 0; i < n; i++)
            {
                arr[i] = new int[i + 1];
                arr[i][0] = 1;
                arr[i][arr[i].Length - 1] = 1;
            }
            for (int i = 2; i < n; i++)
            {
                for (int q = 1; q < arr[i].Length - 1; q++)
                {
                    arr[i][q] = arr[i - 1][q] + arr[i - 1][q - 1];
                }
            }
            return arr;

        }

 static int[][] PasTri(int n)
{
    int[][] triangle = new int[n][];
    for (int i = 0; i < n; i++)
    {
        triangle[i] = new int[i + 1];
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i)
            {
                triangle[i][j] = 1;
            }
            else
            {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
        }
    }
    return triangle;
}

 static int[][] PasTri(int n) 
{
    int[][] array = new int[n][];
    for (int i = 0; i < n; i++){
        array[i] = new int[i+1];
        for (int j = 0; j <= i; j++){
            if (j == 0 || j == i){
                array[i][j] = 1;
            } else {
                array[i][j] = array[i-1][j-1] + array[i-1][j];
            }
        }
    }
    return array;
}

 static int[][] PasTri(int n)
{
    int[][] m = new int[n][];
    for (int i = 0; i < n; i++)
    {
        m[i] = new int[i + 1];
        for (int j = 0; j < m[i].Length; j++)
        {
            m[i][0] = 1;
            m[i][m[i].Length - 1] = 1;
            if (j > 0 && j < m[i].Length - 1)
            {
                m[i][j] = m[i - 1][j - 1] + m[i - 1][j];
            }
        }
    }
    return m;
}

 public static int[][] PasTri(int n)
        {
            int[][] triangle = new int[n][];
            for (int i = 0; i < n; i++)
            {
                triangle[i] = new int[i + 1];
                triangle[i][0] = 1;
                for (int j = 1; j < i; j++)
                {
                    triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
                }
                triangle[i][i] = 1;
            }
            return triangle;
}

 static int[][] PasTri(int n){
    int[][] array = new int[n][];
    for(int i = 0; i < n; i++){
        array[i] = new int[i+1];
        array[i][0] = 1;
        for(int j = 1; j < i; j++){
            array[i][j] = array [i-1] [j-1] + array [i-1][j];
        }
        array[i][i] = 1;
        
    }
    return array;
    
}

 static int[][] PasTri(int n)
        {
            int[][] arr = new int[n][];
            for (int i = 0; i < n; i++)
            {
                arr[i] = new int[i + 1];
                for (int j = 0; j < i + 1; j++)
                {
                    if (j == 0 || j == i)
                    {
                        arr[i][j] = 1;
                    }
                    else
                    {
                        arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
                    }
                }
            }
            return arr;
        }

 static int[][] PasTri(int height){
    int[][] answ = new int[height+1][];
    for(int i = 0; i < height; i++){answ[i] = new int[i+1];}
    answ[0][0] = 1;
    
    for(int row = 0; row < height-1; row++){
        for(int col = 0; col <= row; col++){
            answ[row+1][col] += answ[row][col];
            answ[row+1][col+1] += answ[row][col];
        }
    }
    
    return answ;
}

 static int[][] PasTri(int n)
{
    int[][] m = new int[n][];
    for(int i = 0; i < n; i++)
    {
        m[i] = new int[i+1];
        m[i][0] = m[i][m[i].Length - 1] = 1;
    }
    if(n == 1 || n == 2)
        return m;
    for(int i = 2; i < n; i++)
    {
        for(int j = 1, k = 0; j < m[i].Length - 1; j++, k++)
        {
            m[i][j] = m[i-1][k] + m[i-1][k+1];
        }
    }
    return m;
}

 static int[][] PasTri(int n){
    int[][] tr= new int[n][];
    for (int i=0; i< n; i++){
        tr[i]= new int[i+1];
        tr[i][0]=1;
        for (int j=1; j< i; j++){
            tr[i][j]= tr[i-1][j-1]+tr[i-1][j];
        }
        tr[i][i]=1;
    }
    return tr;
}

 static int[][]PasTri(int n)
{
    int[][] array = new int [n][];
    array[0] = new int[]{1};
    for (int i = 1; i < n; i++)
    {
        array[i] = new int[i + 1];
        int m = 0;
        for (int j = 0; j < i; j++)
        
        {
            array [i][j] = array [i - 1][j] + m;
            m = array [i - 1][j];
        }
        array [i] [i] = m;
    }
    return array;
}

 public static int[][] PasTri(int n) {
            int[][] fucktriangle = new int[n][];
            for(int i = 0; i < n; i++)
            {
                fucktriangle[i] = new int[i + 1];
                fucktriangle[i][0] = 1;

                for(int j = 1; j < i; j++)
                {
                    fucktriangle[i][j]= fucktriangle[i - 1][j-1] + fucktriangle[i - 1][j];  
                }
                fucktriangle[i][i]= 1;
            }
            return fucktriangle;
                }

 public static int[][] PasTri(int n)
{
    int[][] triangle = new int[n][];

    for (int i = 0; i < n; i++)
    {
        triangle[i] = new int[i+1];
        triangle[i][0] = 1;

        for (int j = 1; j < i; j++)
        {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }

        triangle[i][i] = 1;
    }

    return triangle;
}

 static int[][] PasTri(int n) {
    int[][] result = new int[n][];
    result [0] = new int[] { 1 };
    for (int i = 1; i < n; i++) {
        result [i] = new int[i + 1];
        int left = 0;
        for (int j = 0; j < i; j++) {                                       
            result [i][j] = result [i - 1] [j] + left;
            left = result [i - 1] [j];
        }
        result [i] [i] = left;
    }
    return result;
}

 static int[][] PasTri(int n) {
    int[][] arr = new int[n][];
    for (int i = 0; i < n; i++) {
        arr[i] = new int[i+1];
        int tmp1 = arr[i][0];
        for (int j = 0; j <= i; j++) {
            if (j != 0 && j != i) {
                arr[i][j] = arr[i-1][j] + arr[i-1][j-1];
            }
            else {
                arr[i][j] = 1;
            }
        }
    }

    return arr;
}

 static int[][] PasTri(int n) {
  int[][] arr = new int[n][];
  arr[0] = new int[]{1};
  for (int i = 1; i < arr.Length; i++) {
    arr[i] = new int[i + 1];
    arr[i][0] = arr[i][i] = 1;
    for (int j = 1; j < arr[i].Length - 1; j++)
        arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
    }          
  return arr;
}

 static int[][] PasTri(int n)
{
int numRows = n;
    int[][] list = new int[numRows][];
            for (int i = 0; i < numRows; i++)
            {
                list[i] = new int[i+1];
                list[i][0] = 1;
            }  
            for (int i = 1; i < numRows; i++)
            {
                for (int j = 1,f=1; j < list[i-1].Length+1; j++)
                {
                    if (j== list[i - 1].Length)
                    {
                        list[i][f]=1;
                        f++;
                    }
                    else
                    {
                        list[i][f]=list[i - 1][j-1] + list[i - 1][j];
                        f++;
                    }
                }
            }
            return list;
}

 static int[][] PasTri(int n) {
    int[][] t = new int[n][];
    for (int i = 0; i < n; i++) {
        t[i] = new int[i+1];
        t[i][0] = 1;
        for (int j = 1; j < i; j++) {
            t[i][j] = t[i-1][j-1] + t[i-1][j];
        }
        t[i][i] = 1;
    }
    return t;
}

 public static int[][] PasTri(int n)
{
    int[][] pascal = new int[n][];
    for (int i = 0; i < n; i++)
    {
        pascal[i] = new int[i+1];

        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i)
            {
                pascal[i][j] = 1;
            }
            else
            {
                pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
            }
        }
    }
    return pascal;
}

 static int[][] PasTri(int n)
        {
            int[][] mass = new int[n][];
            for(int i = 0; i < n; i++)
            {
                mass[i] = new int[i+1];
            }
            for(int i = 0; i < n; i++)
            {
                mass[i][0] = 1;
                mass[i][mass[i].Length - 1] = 1;
                if(i < 2)
                {
                    continue;
                }
                for (int j = 1; j < mass[i].Length - 1; j++)
                {
                    mass[i][j] = mass[i - 1][j - 1] + mass[i - 1][j];
                }
            }
            return mass;
        }

 public static int[][] PasTri(int n)
{
    int[][] pascal = Enumerable.Range(0, n)
        .Select(i => new int[i+1])
        .ToArray();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i)
            {
                pascal[i][j] = 1;
            }
            else
            {
                pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
            }
        }
    }
    return pascal;
}

 public static int[][] PasTri(int n) {
        int[][] a = new int[n][];
        
        for (int i = 0; i < n; i++) {
            a[i] = new int[i+1];
            a[i][0] = 1;
            
            for (int j = 1; j < i; j++) {
                a[i][j] = a[i-1][j-1] + a[i-1][j];
            }
            
            a[i][i] = 1;
        }
        
        return a;
    }

 static int[][] PasTri(int n){
    int[][] myArray = new int[n][];
    myArray[0] = new int[]{1};
    for(int i = 1;i < n;i++){
        myArray[i] = new int[i + 1];
        int xHelp = 0;
            for(int j = 0;j < i;j++){
                myArray[i][j]= myArray[i-1][j]+xHelp;
                xHelp = myArray[i-1][j];
        }
        myArray [i] [i] = xHelp;
    }
    return myArray;
}

 static int[][] PasTri(int n) {
    int[][] triangle = new int[n][];
    for (int i = 0; i < n; i++) {
        triangle[i] = new int[i+1];
        triangle[i][0] = triangle[i][i] = 1;
        for (int j = 1; j < i; j++)
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
    }
    return triangle;
}

 static int[][] PasTri(int n) {
    int[][] result = new int[n][];
    result [0] = new int[] { 1 };
    for (int i = 1; i < n; i++) {
        result [i] = new int[i + 1];
        int left = 0;
        for (int j = 0; j < i; j++) {                                       
            result [i][j] = result [i - 1] [j] + left;
            left = result [i - 1] [j];
        }
        result [i] [i] = left;
    }
    return result;
}

 static int[][] PasTri(int n)
{
    int[][] triangle = new int[n][];
    for (int i = 0; i < n; i++)
    {
        triangle[i] = new int[i + 1];
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i)
            {
                triangle[i][j] = 1;
            }
            else
            {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
        }
    }
    return triangle;
}

 static int[][] PasTri(int n){
    int[][] result = new int[n][];
    for (int i = 0; i < n; i++)
    {
        result[i] = new int[i+1];
    }
    for (int i = 0; i < n; i++)
    {
        result[i][0] = 1;
        result[i][result[i].Length-1] = 1;
        for (int j = 0; j < result[i].Length - 2; j++)
        {
            if (result[i-1][j + 1] != 0)
            {
                result[i][j+1] = result[i-1][j] + result[i-1][j + 1];
            }
        }
    }
    return result;
}

 static int[][] PasTri(int n){
    int[][] ar = new int[n][];
    for(int i = 0; i < n; i++){
        ar[i] = new int[i + 1];
        for(int j = 0; j <= i; j++){
            if(i == 0 || i == 1){
                ar[i][j] = 1;
            }
            else{
                ar[i][0] = 1;
                ar[i][ar[i].GetUpperBound(0)] = 1;
                for(int k = 1; k < ar[i].GetUpperBound(0); k++){
                    ar[i][k] = ar[i - 1][k] + ar[i - 1][k - 1];
                }
            }

        }
    }
    return ar;
}

 static int[][] PasTri(int n){
    int [][] res=new int[n][];
    for(int i=0;i< n;i++){
        res[i]=new int[i+1];
        res[i][0]=1;
        res[i][res[i].Length-1]=1;
    }
    for(int i=2;i< n;i++){
        for(int j=1;j< res[i].Length-1;j++){
            res[i][j]=res[i-1][j]+res[i-1][j-1];
        }
    }
    return res;
}

 static int[][] PasTri(int n) {
    int[][] result = new int[n][];
    result [0] = new int[] { 1 };
    for (int i = 1; i < n; i++) {
        result [i] = new int[i + 1];
        int left = 0;
        for (int j = 0; j < i; j++) {                                       
            result [i][j] = result [i - 1] [j] + left;
            left = result [i - 1] [j];
        }
        result [i] [i] = left;
    }
    return result;
}

 static int[][] PasTri(int n) {
    int[][] rows = new int[n][]; 
    for (int i = 0; i < n; i++) {
        int[] row = new int[i + 1];
        for (int j = 0; j < i + 1; j++) {
            if (j == 0 || j == i) {
                row[j] = 1;
            } else {
                row[j] = rows[i - 1][j - 1] + rows[i - 1][j];
            }
        }
        rows[i] = row;
    }
    return rows;
}

 static int[][] PasTri(int n) {
    int[][] result = new int[n][];

    for (int i = 0; i < n; i++) {
        result[i] = new int[i + 1];
        result[i][0] = 1;

        for (int j = 1; j < i; j++) {
            result[i][j] = result[i-1][j-1] + result[i-1][j];
        }

        result[i][i] = 1;
    }

    return result;
}


// int[][] n = PasTri(5);

// for (int i = 0; i < n.Length; i++) {
//     for (int j = 0; j < n[i].Length; j++) {
//         Console.Write(n[i][j] + " ");
//     }
//     Console.WriteLine();
// }
// Console.ReadLine();

 static int[][] PasTri(int n)
    {
        int[][] result = new int[n][];
        int[] fact = new int[n];
        fact[0] = 1;
        for (int i = 1; i < n; i++)
        {
            fact[i] = fact[i - 1] * i;
        }
        for (int i = 0; i < n; i++)
        {
            result[i] = new int[i+1];
        }
        for (int i = 0; i < n; i++)
        {
            for(int j = 0; j <= i; j++)
                result[i][j] = fact[i] / (fact[j] * fact[i - j]);
        }
        return result;
    }

 static int[][] PasTri(int n) {
    int[][] array = new int[n][];
    for (int i = 0; i < n; i++) {
        array[i] = new int[i + 1];
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) 
                array[i][j] = 1;
            else
                array[i][j] = array[i - 1][j - 1] + array[i - 1][j];
        }
    }
    return array;
}

 public static int[][] PasTri(int n) {
    int[][] triangle = new int[n][];
    triangle[0] = new int[] { 1 };

    for (int i = 1; i < n; i++)
    {
        triangle[i] = new int[i + 1];
        triangle[i][0] = 1;
        triangle[i][i] = 1;

        for (int j = 1; j < i; j++)
        {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }

    return triangle;
}

 static int[][] PasTri(int n)
{
    // Створення трикутного масиву
    int[][] triangle = new int[n][];
    for (int i = 0; i < n; i++)
    {
        triangle[i] = new int[i + 1];
    }

    // Заповнення трикутника Паскаля
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i) // крайні елементи рядка дорівнюють 1
            {
                triangle[i][j] = 1;
            }
            else
            {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]; // інакше - сума двох попередніх
            }
        }
    }

    return triangle;
}

 static int[][] PasTri(int n)
            {
            
            int[][] res = new int[n][];
            res[0] = new int [1];
            res[0][0] = 1;
            res[1] = new int[2];
            res[1][0] = 1; res[1][1]=1;
                for(int i=2;i< n; i++)
                {
                res[i] = new int[res[i - 1].Length + 1];
                res[i][0] = 1;
                res[i][res[i].Length - 1] = 1;
                    for (int j = 1; j < res[i].Length - 1; j++)
                    {
                        res[i][j] = res[i - 1][j-1]+res[i-1][j];
                    }
                }
                return res;
            }

 static int[][] PasTri(int n)
{
    int[][] triangle = new int[n][];
    for (int i = 0; i < triangle.Length; i++)
    {
        triangle[i] = new int[i + 1];
        triangle[i][0] = 1;
        triangle[i][triangle[i].Length - 1] = 1;
    }
    for (int i = 2; i < triangle.Length; i++)
    {
        for (int j = 1; j < triangle[i].Length - 1; j++)
        {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
    
    return triangle;
}

 static int[][] PasTri(int n)
{
    int[][] arr = new int[n][];
    for (int i = 0; i < n; i++)
    {
        arr[i] = new int[i + 1];
        for (int c = 0; c <= i; c++)
            arr[i][c] = factorial(i) / (factorial(c) * factorial(i - c));
    }
    return arr;
}

public static int factorial(int n)
{
    int x = 1;
    for (int j = 1; j <= n; j++) x *= j;
    return x;
}

 static int[][] PasTri(int n) {

    int[][] Tri = new int[n][];
    
    for (int i = 0; i < n; i++) {
                
        Tri[i] = new int[i + 1];
        Tri[i][0] = Tri[i][i] = 1;

        for (int j = 1; j < i; j++) {
            Tri[i][j] = Tri[i - 1][j - 1] + Tri[i - 1][j];
        }
    }
    return Tri;
}

 static int[][] PasTri(int n) {
    int[][] result = new int[n][];
    result [0] = new int[] { 1 };
    for (int i = 1; i < n; i++) {
        result [i] = new int[i + 1];
        int left = 0;
        for (int j = 0; j < i; j++) {                                       
            result [i][j] = result [i - 1] [j] + left;
            left = result [i - 1] [j];
        }
        result [i] [i] = left;
    }
    return result;
}

 static int[][] PasTri(int n) {
    int[][] res = new int[n][];

    for (int i = 0; i < n; i++) {
        res[i] = new int[i + 1];
        res[i][0] = 1;
        for (int j = 1; j < i; j++)
            res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
        res[i][i] = 1;
    }
    return res;
}

 static int[][] PasTri(int n)
{
    int[][] pasc = new int[n][];

    for (int i = 0; i < n; i++)
    {
        pasc[i] = new int[i + 1];     
        pasc[i][0] = 1;
        pasc[i][^1] = 1;

        if (i < 2)
        {
            continue;
        }

        for (int j = 1; j < pasc[i].Length - 1; j++)
        {
            pasc[i][j] = pasc[i - 1][j - 1] + pasc[i - 1][j];
        }
    }

    return pasc;
}

 static int[][] PasTri(int n)
{
    int[][] triangle = new int[n][];
    for (int i = 0; i < triangle.Length; i++)
    {
        triangle[i] = new int[i + 1];
        triangle[i][0] = 1;
        triangle[i][triangle[i].Length - 1] = 1;
    }
    for (int i = 2; i < triangle.Length; i++)
    {
        for (int j = 1; j < triangle[i].Length - 1; j++)
        {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
    
    return triangle;
}

 static int[][] PasTri(int n)
{
    int[][] a = new int[n][];
    for (int k = 0; k < n; k++)
    {
        a[k] = new int[k + 1];
        a[k][0] = 1;
        for (int i = 1; i < k; i++)
        {
            a[k][i] = a[k - 1][i - 1] + a[k - 1][i];  
        }
        a[k][k] = 1;
    }
    return a;
}

 static int[][] PasTri(int n)
{
    int[][] triangle = new int[n][];
    
    for (int i = 0; i < n; i++)
    {
        triangle[i] = new int[i + 1];
        triangle[i][0] = 1;
        
        for (int j = 1; j < i; j++)
        {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
        
        triangle[i][i] = 1;
    }
    return triangle;
}

static int[][] PasTri(int n) {
    int[][] result = new int[n][];
    for(int i = 0; i < n; i++) {
        result[i] = new int[i+1];
        result[i][0] = 1;
        result[i][i] = 1;
        for(int j = 1; j < i; j++) {
            result[i][j] = result[i-1][j-1] + result[i-1][j];
        } 
    }
    return result;
}

 static int[][] PasTri(int n)
{
    int[][] arr = new int[n][];
    for (int i = 0; i < n; i++)
    {
        arr[i] = new int[i + 1];
        for (int j = 0; j < i + 1; j++)
        {
            if (j == 0 || j == i)
                arr[i][j] = 1;
            else 
                arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
        }
    }
    return arr;
}

 static int[][] PasTri(int n)
    {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++)
        {
            triangle[i] = new int[i + 1];
        }

        triangle[0][0] = 1;
        if (n > 1)
        {
            triangle[1][0] = 1;
            triangle[1][1] = 1;
        }

        for (int i = 2; i < n; i++)
        {
            triangle[i][0] = 1;
            for (int j = 1; j < i; j++)
            {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
            triangle[i][i] = 1;
        }

        return triangle;
    }

 static int[][] PasTri(int n)
{
    int[][] arrey = new int[n][];
    for (int i = 0; i < n; i++)
    {
        int[] arrey1 = new int[n];
        arrey1[0] = 1;
        arrey[i] = arrey1;
    }
    for (int j = 1; j < n; j++)
    {
        for (int k = 1; k < n; k++)
        {
            arrey[j][k] = arrey[j - 1][k - 1] + arrey[j - 1][k];
        }
    }
    return arrey;
}