def fastmodel(a: int, n: int, p: int) -> int:
    if n == 0:
        return 1
    t = (a ** 2) % p
    temp = fastmodel(t, n // 2, p)
    if (n & 1) == 1:
        temp = (temp * a) % p
    return temp


if __name__ == "__main__":
    print(fastmodel(3, 1254906, 10))

0d894111b86be4cd4b6c255a810fdec388b5d314
<mask token>

def fastmodel(a: int, n: int, p: int) ->int:
    if n == 0:
        return 1
    t = a ** 2 % p
    temp = fastmodel(t, n // 2, p)
    if n & 1 == 1:
        temp = temp * a % p
    return temp


<mask token>

def fastmodel(a: int, n: int, p: int) ->int:
    if n == 0:
        return 1
    t = a ** 2 % p
    temp = fastmodel(t, n // 2, p)
    if n & 1 == 1:
        temp = temp * a % p
    return temp


if __name__ == '__main__':
    print(fastmodel(3, 1254906, 10))

def fastmodel(a: int, n: int, p: int) -> int:
    if n == 0:
        return 1
    t = (a ** 2) % p
    temp = fastmodel(t, n // 2, p)
    if (n & 1) == 1:
        temp = (temp * a) % p
    return temp


if __name__ == "__main__":
    print(fastmodel(3, 1254906, 10))
