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