you may possibly get along without modular exponentiation The product n does not have to be computed. You just need to memorise how many of which prime factors you have,
and then compute the sum of all different subsets of them plus the number of subsets. Subtract 1000000007 whenever your results get larger.
And use Erastosthenes to find teh first 10000 prime numbers. YOu may do this in advance and use a fixed array to speed things up. Or just pick them form a web page.
Am 04.01.2017 um 16:28 schrieb Ką Mykolas: