Pascal's triangle

//To print the full pascal traingle TC. O(n^2)
class Solution:
    def generate(self, n: int):
        arr = [[] for _ in range(n)]

        for i in range(n):
            arr[i] = [0] * (i + 1)          # make row of required size
            arr[i][0] = arr[i][i] = 1       # first and last element are always 1

            for j in range(1, i):           # fill middle elements
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j]

        return arr


//To print a row of pascal's traingle
/*
Logic:
If you observe then you will find that the nth row elements are :
nc0,nc1,nc2,nc3,nc4,nc5....ncn(where n is 1 based indexing)
so we can calculate nc0,nc1,nc2...one by one.

Improvisation:
NCr = (NC(r-1) * (N - r + 1)) / r where 1 ≤ r ≤ N
so if NC0=1 keep it in prev variable
so NC1=1*(N-1+1) and so on.

class Solution:
    def generate(self, sz: int) -> List[List[int]]:
        ans=[]
        for i in range(sz):
            temp=[1]
            n=i
            for j in range(1,n+1):
                val=(temp[-1]*(n-j+1))//j
                temp.append(val)
            ans.append(temp)
        return ans

*/

/*
Same above approach if row needed considering large number as the modulo of 10^9+7
*/
MOD = 10**9 + 7

def gcd_extended(a, b):
    # Base case
    if a == 0:
        return b, 0, 1

    gcd, x1, y1 = gcd_extended(b % a, a)

    # Update x and y
    x = y1 - (b // a) * x1
    y = x1

    return gcd, x, y


def mod_inverse(b, m):
    gcd, x, _ = gcd_extended(b, m)

    # If inverse doesn't exist
    if gcd != 1:
        return -1

    return (x % m + m) % m


def mod_divide(a, b, m):
    a %= m
    inv = mod_inverse(b, m)
    return (a * inv) % m


class Solution:
    def nthRowOfPascalTriangle(self, n: int):
        n -= 1  # convert to 0-based
        prev = 1
        res = [1]

        for i in range(1, n + 1):
            # nCr = nC(r-1) * (n - r + 1) / r
            curr = (prev * (n - i + 1)) % MOD
            curr = mod_divide(curr, i, MOD)
            res.append(curr)
            prev = curr

        return res