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