def p1():
    VALUE_MASK = 0xffff
    generatorA = 634
    generatorB = 301
    cpt = 0

    for x in xrange(0, 40000000):
        generatorA = (generatorA * 16807) % 2147483647
        generatorB = (generatorB * 48271) % 2147483647
        if (VALUE_MASK & generatorA) == (VALUE_MASK & generatorB):
            cpt += 1
    return cpt


def p2():
    VALUE_MASK = 0xffff
    generatorA = 634
    generatorB = 301
    cpt = 0
    valuesA = []
    valuesB = []
    while min(len(valuesB), len(valuesA)) < 5000000:
        generatorA = (generatorA * 16807) % 2147483647
        generatorB = (generatorB * 48271) % 2147483647
        if generatorA % 4 == 0:
            valuesA.append(generatorA)
        if generatorB % 8 == 0:
            valuesB.append(generatorB)

    for x in xrange(0, min(len(valuesB), len(valuesA))):
        if (VALUE_MASK & valuesA[x]) == (VALUE_MASK & valuesB[x]):
            cpt += 1

    return cpt