Numbers Tell

Limits: 2s, 1.0 GB

Ok, so in this problem, you will be given N and M, how many ways we can take two numbers from 1 to N so that their absolute difference is divisible by M. As the answer can be quite big, give the modulo of the answer by 1000,000,009.

This is a companion discussion topic for the original entry at