# Solve the Congruency

Given integers $R,M$ with $M\neq 0$, let $S(R,M)$ denote the smallest positive integer $x$ satisfying the congruence $Rx \equiv 1 \pmod{M}$ if such an $x$ exists. If such an $x$ does not exist, put $S(R,M)=0$.

Each line of this text file contains a pair of space separated integers representing $R$ and $M$, respectively.

Let L be the list of integers whose $k$-th element is the value of $S(R,M)$, where $R$ and $M$ are taken from the $k$-th line of the text file.

Let T be the sum of all elements of L. What are the last three digits of T?

×