print((function (f)
	return tostring(f(1000007ULL,io.stdin:read("*n")+0ULL)):sub(1,-4)
end)(function (m, n)
	return n%2==0 and (((n/2+2)%m)*(n/2%m))%m or (((n/2+3)%m)*(n/2%m)+1)%m
end))