There are at most \(M\) possible values of \(A_i\). Therefore, the sequence starts to repeat at some point. Precalculate

• the number of terms before the cycle starts and their sum, and
• the number of terms in the cycle and their sum,

and calculate three values: the sum of elements before the cycle, the sum of repeating elements, and the sum of remaining elements; then the problem could be solved in a total of \(O(M)\) time. Note that it may reach to the \(N\)-th element before entering the cycle.

\( \)

Example: when \(M=449, A_1=2,N=1000\)

\(A=\{2,4,16,256,431,324,359,18,324,359,\ldots\}\), and

• elements before the cycle: \(\{2,4,16,256,431\}\)
• elements in the cycle: \(\{324,359,18\}\),

so the sum of first \(1000\) elements can be calculated as \((2+4+16+256+431) + (324+359+18)\times 331 + (324+359)\).