def multiply_by_mod(matrix1, matrix2, mod):
    matrix = [[0,0],[0,0]]
    matrix[0][0] = (matrix1[0][0] * matrix2[0][0] + matrix1[0][1] * matrix2[1][0]) % mod
    matrix[0][1] = (matrix1[0][0] * matrix2[0][1] + matrix1[0][1] * matrix2[1][1]) % mod
    matrix[1][0] = (matrix1[1][0] * matrix2[0][0] + matrix1[1][1] * matrix2[1][0]) % mod
    matrix[1][1] = (matrix1[1][0] * matrix2[0][1] + matrix1[1][1] * matrix2[1][1]) % mod

    return matrix


def fast_pwr(matrix, deg, mod):
    if deg == 1 or deg == 0:
        return matrix

    if deg % 2 == 0:
        f = fast_pwr(matrix, deg/2, mod)
        return multiply_by_mod(f, f, mod)
    if deg % 2 == 1:
        f = fast_pwr(matrix, (deg - 1), mod)
        return multiply_by_mod(f, matrix, mod)