#!/usr/bin/env python

###def generatorA():
###	while(True):
###		generatorA.prev_value *= 16807
###		generatorA.prev_value %= 2147483647
###		return generatorA.prev_value
###generatorA.prev_value = 116

def generatorA_p2():
	while(True):
		generatorA_p2.prev_value *= 16807
		generatorA_p2.prev_value %= 2147483647
		if generatorA_p2.prev_value % 4 == 0:
			return generatorA_p2.prev_value
generatorA_p2.prev_value = 116

###def generatorB():
###	generatorB.prev_value *= 48271
###	generatorB.prev_value %= 2147483647
###	return generatorB.prev_value
###generatorB.prev_value = 299


def generatorB_p2():
	while(True):
		generatorB_p2.prev_value *= 48271
		generatorB_p2.prev_value %= 2147483647
		if generatorB_p2.prev_value % 8 == 0:
			return generatorB_p2.prev_value
generatorB_p2.prev_value = 299

###judge_total = sum((1 if ('{0:032b}'.format(generatorA())[-16:]=='{0:032b}'.format(generatorB())[-16:]) else 0 for i in [None]*40000000))
###
###answer1 = judge_total
###
###print("Part 1: " + str(answer1))

judge_total_p2 = sum((1 if ('{0:032b}'.format(generatorA_p2())[-16:]=='{0:032b}'.format(generatorB_p2())[-16:]) else 0 for i in [None]*5000000))

answer2 = judge_total_p2

print("Part 2: " + str(answer2))