The Multiplication

The main idea is: for each k, pre-calculate all possible values of ((1+k) × (1+2k) × ... × (1+ik)) mod m, where ik ≤ 227. But to store them, we need a huge amount of memory. So, we will store the values maintaining a period. For example, if we maintain a period of length = 1000, and we store the values in an array called pre[], then for each k,

pre[1] will store ((1+k) × (1+2k) × ... × (1+1000k)) mod m

pre[2] will store ((1+k) × (1+2k) × ... × (1+2000k)) mod m

And, so on...

If we need to calculate ((1+k) × ... × (1+2115k)), then we can use the value stored in pre[2] and calculate the rest manually. As we are maintaining a period of length = 1000, we don’t need to run more than 1000 loops to perform that rest calculation.

The rest of the task is pretty simple. They are for the readers to find out.

Note: The length of the period should not be much large. In that case, a large amount of loop will be needed in each test case and that will give a CPU Limit Exceeded verdict.