So, funny story: I spent many hours over the last two days poring over identities involving binomial coefficients, in hopes of massaging a sum that took O(K^2) into a sum that takes O(K). I assumed that there had to be some kind of combinatorial trick involving Pascal's triangle, because otherwise how could this challenge be possible? Anyway, I finally found one, and everything passes.

Lo and behold, the editorial mentions the same formula that I ended up finding --- as an alternative solution (submitted by bayleef). The intended method of solution from the editorial did not occur to me even once, and I'm sure I wouldn't ever have considered it even if I spent another two weeks on this problem. :-) Perhaps if I were more familiar with particular large primes, I might have taken the "unusual" modulus as a hint, but it was totally lost on me. :-)

Anyway, kevinsogo mentions in the editorial that he couldn't see a proof that bayleef's formula gives the same answer as the naive (and slow) formula involving Stirling numbers; the comments in my submission outline the combinatorial argument that shows why the two formulas are equivalent.

Please feel free to drop me a line if I can offer any assistance with solving this challenge in an apparently completely unintended way. :-)