use bigint;print+bnok$m(<>/1e3%($m=0+<>))%1e9