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