My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <vector>
       
 
       
// powmod's code was taken from my toolbox

       
unsigned int powmod(unsigned int base, unsigned int exponent, unsigned int modulo)
       
{
       
  unsigned int result = 1;
       
  while (exponent > 0)
       
  {
       
    // fast exponentation:
       
    // odd exponent ? a^b = a*a^(b-1)
       
    if (exponent & 1)
       
      result = (result * (unsigned long long)base) % modulo;
       
 
       
    // even exponent ? a^b = (a*a)^(b/2)
       
    base = (base * (unsigned long long)base) % modulo;
       
    exponent >>= 1;
       
  }
       
  return result;
       
}
       
 
       
int main()
       
{
       
  // from 1 to 250250
       
  unsigned int limit  = 250250;
       
  // numbers divisible by 250 => residue/remainder is zero
       
  unsigned int modulo = 250;
       
 
       
  std::cin >> limit >> modulo;
       
 
       
  // compute all (i^i) % 250
       
  std::vector<unsigned int> residues;
       
  for (unsigned int i = 0; i <= limit; i++)
       
    residues.push_back(powmod(i, i, modulo));
       
 
       
  // 10^16
       
  const auto SixteenDigits = 10000000000000000ULL;
       
 
       
  // how many sets of the current size have which residue
       
  std::vector<unsigned long long> current(modulo + 1, 0);
       
  // the empty set is divisible by 250 (and there's only one empty set)
       
  current[0] = 1;
       
 
       
  // and the same for all sets with one more element
       
  auto last = current;
       
 
       
  // step-by-step add each number ...
       
  for (unsigned int i = 1; i <= limit; i++)
       
  {
       
    // ... to each set
       
    for (unsigned int j = 0; j < modulo; j++)
       
    {
       
      // only possible if there was at least one set
       
      if (last[j] == 0) // these two lines can be removed, too,
       
        continue;       // they are no major performance improvement
       
 
       
      // how does the new number change the residue of the set ?
       
      auto newResidue = residues[i] + j;
       
      // wrap around
       
      if (newResidue >= modulo) // same as newResidue %= modulo but a bit faster
       
        newResidue -= modulo;
       
 
       
      // add the number of all "old" sets to the new residue
       
      current[newResidue] += last[j];
       
      // keep only the last 16 digits
       
      current[newResidue] %= SixteenDigits;
       
    }
       
 
       
    // copy data for next iteration
       
    last = current;
       
  }
       
 
       
  // final value is the first element (where residue is 0 => divisible by 250)
       
  auto result = current[0];
       
  // ... but don't count the empty set
       
  if (result == 0)
       
    result = SixteenDigits;
       
  result--;
       
 
       
  // and display it
       
  std::cout << result << std::endl;
       
  return 0;
       
}

This solution contains 14 empty lines, 22 comments and 2 preprocessor commands.