def shuffle(L, sp):
	l1 = L[:sp]
	l2 = L[sp:]
	sh = []
	#for i in range(len(l1)):
	#	sh = [l2[-1-i], l1[-1-i]] + sh
	sh = l1 + l1
	sh[::2] = L[-len(l1):]
	sh[1::2] = l1
	return l2[:len(l2)-len(l1)] + sh

def do_mapping(v1, v_map):
	v2 = v1[:]
	for i in range(len(v1)):
		v2[i] = v1[v_map[i]]
	return v2

def fast_search(nCards, iCut, n):
	original = list(range(nCards))
	L = list(range(nCards))
	precomputed = []
	c1 = 1
	for i in range(n):
		precomputed.append(L)
		L = shuffle(L, iCut)
		if L == original:
			return c1
		c1+=1
	#print(precomputed)
	#print("asdf", L==precomputed[9972], L, precomputed[9972])
	#big_shuffles = []
	count = 0
	deck = L[:]
	monitor = 1
	while deck not in precomputed:
		deck = do_mapping(deck, L)
		#big_shuffles.append(deck)
		count+=1
		#print(count*n)
		if count*n>monitor:
			print(monitor, count*n)
			monitor*=2
	j = 0
	while j<n:
		if precomputed[j]==deck:
			break
		j+=1
	#print(deck, count*n-j, count-1, n, j)
	return (count+1)*n-j

print(fast_search(1002,101,400000))