def func_exp(func, p: int):
    """
    Exponentiates a function. In other words, returns a function that will be
    executed p times when called.

    Paramaters
    ----------
    func : a -> a
        A function going from some type to that same type.
    Returns
    -------
    a -> a
        A function that will run the parameter p times.
    """

    def ret(x):
        for i in range(p):
            x = func(x)
        return x

    return ret


def average(lst: list[int]) -> int:
    """
    Takes the average of a list of ints.

    Parameters
    ----------
    lst : list[int]
        The list to take an average of.

    Returns
    -------
    int : the average of that list.
    """
    return sum(lst) / len(lst)


def derive_sequence(lst: list[int]) -> list[int]:
    """
    Takes the discrete derivative of a sequence of ints.

    Parameters
    ----------
    lst : list[int]
        The list to derive.

    Returns
    -------
    list[int] : The discrete derivative of lst.
    """
    ret = []
    for idx, n in enumerate(lst[1:]):
        ret.append(n - lst[idx])
    return ret


def pairwise_transform(lst: list[int], func) -> list:
    """
    Transforms all the adjacent values in lst using func.

    Parameters
    ----------
    lst : list[int]
        The list to transform.

    func : (int, int) -> a
        A function that takes two ints and produces some result.

    Returns
    -------
    list : A list of the result of applying func to consecutive elements of lst.
    """
    ret = []
    for idx, n in enumerate(lst[1:]):
        ret.append(func(n, lst[idx]))
    return ret


def remove_repeats(lst: list) -> list:
    """
    Removes repeated consecutive elements in a sequence.

    Parameters
    ----------
    lst : list
        The list to verify.

    Returns
    -------
    list : A list containing non-repeated elements of lst.
    """
    if len(lst) == 0:
        return []
    ret = [lst[0]]
    for e in lst:
        if ret[-1] != e:
            ret.append(e)
    return ret

def sliding_window_sum(vals: list[int]) -> list[int]:
    """
    Computes the sliding window sum of vals.

    Parameters
    ----------
    vals : list[int]
        The array to compute.

    Returns
    -------
    list[int] : The sliding window sum of vals.
    """
    ret = []
    for idx, i in enumerate(vals[1:]):
        if idx == len(vals) - 2:
            ret.append(i + vals[0])
        else:
            ret.append(i + vals[idx + 2])
    return ret


def sliding_window(vals: list[int], f) -> list[int]:
    """
    BUG: Doesn't actually work.
    Applies f as a sliding window to vals.

    Parameters
    ----------
    vals : list[int]
        The array to run a sliding window over

    f : (int, int) -> int
        A function that takes two ints and produces an int.

    Returns
    -------
    list[int] : An array resulting from applying f to consecutive elements of
    vals.
    """
    ret = []
    for idx, i in enumerate(vals[1:]):
        ret.append(f(vals[idx], i))
    return ret

def choose(n: int, k: int) -> int:
    """
    Calculates the combinations of n choose k.
    https://en.wikipedia.org/wiki/Combination

    Parameters
    ----------
    n : int
        The size of subsets of k.

    k : int
        The size of the larger set.

    Returns
    -------
    int : n choose k.
    """
    if k > n: return 0
    if k == 0: return 1
    if k == 1: return n
    return factorial(n) / (factorial(n - k) * factorial(k))


def ballot(k: int, l: int) -> int:
    """
    The ballot function for k, l.
    https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem

    Parameters
    ----------
    k : int

    l : int

    Returns
    -------
    int
    """

    return (k - l + 1) / (k + 1) * binomial(k + l, k)


def callot(n: int, k: int) -> int:
    """
    The modified ballot function defined in the Glass Wagner paper.

    Parameters
    ----------
    n : int

    k : int

    Returns
    -------
    int
    """
    return ballot(n - 1, n - k)


def insert_at(arr: list, i: int, x) -> list:
    """
    Inserts x at index i in list arr.

    Parameters
    ----------
    arr : list
        The list to insert into.

    i : int
        The index to insert at.

    x : a
        The value to insert.

    Returns
    -------
    list : A list with x inserted at position i.
    """
    return arr[0:i] + [x] + arr[i:]

def catalan(n: int) -> int:
    """
    Computes the n'th Catalan number.
    https://en.wikipedia.org/wiki/Catalan_number

    Parameters
    ----------
    n : int
        The index in the sequence of Catalan numbers to retrieve.

    Returns
    -------
    int : The n'th Catalan number.
    """
    return factorial(2 * n) / (factorial(n + 1) * factorial(n))

def pairwise_sum(v1: list[int], v2: list[int]) -> list[int]:
    """
    Sums adjacent elements in v1 and v2.

    Parameters
    ----------
    v1 : list[int]
        A list of ints to sum.

    v2 : list[int]
        A list of ints to sum.

    Returns
    -------
    list[int] : The result of adding each int in v1 with each int in v2.
    """
    return list(map(lambda x: x[0] + x[1], zip(v1, v2)))

def characteristic(n: int, i: int) -> list[int]:
    """
    Creates the n-dimensional characteristic vector of i.

    Parameters
    ----------
    n : int
        The amount of dimensions for the vector.

    i : int
        The number to fill the vector with.

    Returns
    -------
    list[int] : The n-dimensional characteristic vector of i.
    """
    ret = [0] * n
    ret[i] = 1
    return ret

def load_file(file_path: str):
    f = open(file_path, "r")
    content = eval(f.read())
    return content

def mod_mul(a: int, b: int, m: int) -> int:
    return ((a % m) * (b % m)) % m


def mod_pow(base: int, exp: int, m: int) -> int:
    ret = 0
    if m != 1:
        ret = 1
        for e in range(0, exp):
            ret = (base * ret) % m

    return ret

# def mod_pow_bin(base: int, exp: int, m: int) -> int:

def is_primitive_root(p: int, alpha: int) -> bool:
    for exp in range((p - 1) // 2):
        if mod_pow(alpha, exp, p) == p - 1:
            return False
    return mod_pow(alpha, (p - 1) // 2, p) == p - 1

def primitive_roots(p: int) -> list[int]:
    ret = []
    for i in range(p):
        if is_primitive_root(p, i):
            ret.append(i)

    return ret

def seq(p: int, alpha: int) -> list[int]:
    ret = []
    i = 1
    base = alpha
    while base != 1:
        base = mod_pow(alpha, i, p)
        ret.append(base)
        i += 1
    return ret

def naive_match(p: int, lst: list[int]) -> list[int]:
    ret = []
    for x in lst:
        for idx, e in enumerate(lst, 1):
            if e + x == p + 1:
                ret.append(idx)
    return ret

def stride_difference(lst: list[int], stride: int, cols = []) -> list[int]:
    ret = []
    l = len(lst)
    lst = lst + cols + lst
    for idx in range(l):
        x = lst[idx]
        y = lst[(idx + stride) % len(lst)]
        ret.append(y - x)
    return ret

def lempel_sd(lst: list[int], stride: int) -> list[int]:
    diffs = stride_difference(lst, stride, [0])
    diffs[-stride] = '*'
    diffs.append('*')
    diffs.append(f"k = {stride}")
    return diffs

def diff_square(p: int, alpha: int) -> list[list[int]]:
    ret = []
    half = p - 1 # (p - 1) // 2 + 1
    for i in range(1, half):
        ret.append(lempel_sd(naive_match(p, seq(p, alpha)), i))
    return ret

def diff_rect(p: int, alpha: int) -> list[list[int]]:
    ret = []
    for i in range(1, p - 1):
        ret.append(stride_difference(seq(11, 2), i))
    return ret

def ints(lst) -> list[int]:
    return list(filter(lambda x: type(x) == int, lst))

def sieve_of_eratosthenes(limit: int) -> list[int]:
    is_prime = [True] * (limit + 1)
    p = 2
    while p * p <= limit:
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
        p += 1
    primes = [p for p in range(2, limit + 1) if is_prime[p]]
    return primes

#primes = sieve_of_eratosthenes(1000)

def mod_seq(lst: list[int], mod: int) -> list[int]:
    return list(map(lambda x: x % mod, lst))

def mod_ast(lst: list[int], mod: int) -> list[int]:
    ret = []
    for i in lst:
        if (type(i) == int):
            ret.append(i % mod)
        else:
            ret.append(i)

def is_costas(lst: list) -> bool:
    return False

def lempel3d(p: int, alpha: int) -> list[list[list[int]]]:
    return [[[0]]]