**Problem link** : https://www.codechef.com/ISCC2017/problems/SEQUA

Can anyone help me for the above question, i am currently stuck up here.

So basically we need to find 1^1 + 2^2 + 3^3 + … + N^N mod M.

Hence, if N <= 1000 , Then i just did a brute force.

but if N > 1000, Then i observed that there will be a series of repetition, lets take it with an example.

Suppose N = 16, M = 4

0 1 2 3 == **(0^0 + 1^1 + 2^2 + 3^3)** == **(0^0 + 1^1 + 2^2 + 3^3)**

4 5 6 7 == **((4%4)^4 + (5%4)^5 + (6%4)^6 + (7%4)^7)** == **(0^4 + 1^5 + 2^6 + 3^7)**

8 9 10 11 == **((8%4)^8 + (9%4)^9 + (10%4)^10 + (11%4)^11)** == **(0^8 + 1^9 + 2^10 + 3^11)**

12 13 14 15 == **((12%4)^12 + (13%4)^5 + (14%4)^6 + (15%4)^7)** == **(0^12 + 1^13 + 2^14 + 3^15)**

16 == **(16%4)^12** == **(0^16)**

Hence i reduced this to calculating sum of gp mod M.

But i could not further proceed for this question, can some one help me out please?