VERYHARD: How to get AC in this?

I have been preparing for Codechef Advance level certification exam. I came across this problem VERYHARD. Link - VERYHARD.

I have applied 3 approches to solve this problem:

  1. BRUTE FORCE - 30pts
  2. SEGMENT TREES - 30pts
  3. FENWICK TREE - 44pts

In 2nd and 3rd approach I made k trees (0,k-1) for each modulus value and stored the count. What approach should I use to get 100pts?

I used segment tree with the same approach and it got accepted. There might be some flaws in your code.