#!/usr/bin/env python3

from functools import reduce

deal  = lambda: (-1, -1)
dealN = lambda n: (n, 0)
cutN  = lambda n: (1, -n)
id    = (1, 0)

instructions = {"deal into new stack" : deal,
                "deal with increment" : dealN,
                "cut" :                 cutN
               }

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comp(ab, cd, mod):
    a, b = ab
    c, d = cd
    return ((a*c) % mod, (a*d + b) % mod)

def apply(ab, x, mod):
    a, b = ab
    return (a*x + b) % mod

def inverse(ab, mod):
    a, b = ab
    x = modinv(a, mod)
    return (x, (-b * x) % mod)

def powcomp(ab, pw, mod):
    a, b = ab
    return (pow(a, pw, mod), ((pow(a, pw, mod) - 1) * modinv(a-1, mod) * b) % mod)

def parse(line):
    for inst in instructions.keys():
        if line[:len(inst)] == inst:
            return instructions[inst](*map(int, line[len(inst):].split()))
    return NotImplemented

def compile(program, deck):
    return reduce(lambda f1, f2: comp(f2, f1, deck), program, id)


def preproc(puzzle_input):
    return list(map(parse, puzzle_input.split('\n')))

def partI(program):
    deck = 10007
    shuffle = compile(program, deck)
    return apply(shuffle, 2019, deck)

def partII(program):
    deck = 119315717514047
    pw   = 101741582076661
    shuffle = compile(program, deck)
    invshuffle = inverse(shuffle, deck)

    repeated = powcomp(invshuffle, pw, deck)
    return apply(repeated, 2020, deck)