We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has exactly km satisfying assignments, for some integer k. We prove that for all primes p, except for possibly one of them, MODp-Sat is not solvable in n^c time and n^{o(1)} space on RAMs, for c > 1 satisfying c^3 - c2 - 2c + 1 < 0 (c < 1.801 suffices). That is, there is at most one prime p that does not satisfy the lower bound. Note that such a lower bound does not follow from the Sat time-space tradeoffs, as we do not know of an efficient deterministic reduction from Sat to MODp-Sat.

The result is non-constructive, in that it does not provide an explicit prime for which the lower bound holds. However, we can prove that the same limitation holds for Sat and MOD6-Sat, as well as MODm-Sat for any composite m that is not a prime power. Our main tool is a general method for rapidly simulating deterministic RAM computations with restricted space, by counting the number of solutions to NP predicates modulo primes. The simulation converts an ordinary RAM into a 'canonical one' that runs in roughly the same amount of time and space, yet its configuration sequences have nice properties suitable for counting.