f = dict()
f[0] = f[1] = 1
val[1] = 1
i = 2
while i < 5000:
	t = (f[i-1] * i) % 1000000009
	if val.has_key(t):
		print "i= %d" % i
		break
	val[t] = i
	f[i] = t
	i+=1