local ffi = require 'ffi'
local C = ffi.C
ffi.cdef 'int printf(const char *, ...);'

C.printf("%lu\n", (function (m, n)
	local t=n/2
	return n%2==0 and (((t+2)%m)*(t%m))%m or (((t+3)%m)*(t%m)+1)%m
end)(1000007ULL, io.stdin:read("*n")+0ULL))