Given two numbers $N$ and $M$, we need to find the remainder when $111 \cdots1$ ($N$ times) is divided by $M$. Here $N$ can go up to $10^{16}$ and $M$ up to $10^9$.
How to solve this problem?
Example: Let $N=5$ and $M=18$. Then answer is $5$ as $11111\%18 = 5$.
Since $N$ only goes up to $10^{16}$, and $M$ fits into 32 bits you can solve this problem in a matter of seconds on a computer that supports 64 bit integers. First solve for the modulus $A$ of $10^8$ ones modulo $M$, by iteratively multiplying by $10$ and adding $1$ and then taking the modulus modulo $M$. Also solve for $B = 10^{10^8 +1}$ modulo $M$. Then build up the answer for a string of ones of length within $10^8$ ones of $N$, by starting with $A$ and then iteratively multiplying by $B$ and adding $A$. You will have to do this at most $10^8$ times since $N \leq 10^{16}$. Then, however may ones are left over, $C < 10^8$, calculate $B' = 10^{C+1}$ modulo $M$ and a string of $C$ ones modulo $M$ (call it $A' $, just like you computed $A$ and $B$. Then multiply your answer by $B'$ and add $A'$ and compute the modulus modulo $M$, and you are done. The total number of operations required is on the order of $10^9$ so this should run very fast on a computer.
Updated with Example: N=13, M=13. The square-root of $N = 13$ rounded down is 3, so we will compute a string of 3 1's (111) modulo 13 and also $10^{3+1} = 1000$ modulo 13. We start with 1, multiply by 10 and add 1 to get 11 which is -2 modulo 13, then multiply by 10 and add 1 to get -19 which is 7 modulo 13. So 111 = 7 modulo 13. Similarly we have 100 = 10*10 = (-3)*(-3) = 9 = -4 modulo 13, and 1000 = (100)10 = (-4)(-3) = 12 = -1 modulo 13. So now we start with 111 which is 7 modulo 13, and multiply by 1000 which is -1 modulo 13 to get -7, and then we add 111 which is 7 to get 0 modulo 13. Repeating this twice to get a string of 12 1's, we again get 0 modulo 13. Now there is only one 1 left, so we multiply by 10 and add 1 to get a final answer of 1 modulo 13.