Did it via DP, but there wasn't enough memory to do a full DP; could only memoize SOME steps. You know you're hacking when your code starts with

typedef unsigned int ulong;