How Many bases? (UVa Live Archive Asia - Site 9 (Bangladesh) - 2009/2010)

N^Mの数値を基底bで表した時に末尾に0がちょうどT個続く基底は何個あるか？
1<=N<=10^8
0< M<=10^7
0< T<=10^4

N^Mを素因数分解し各素因数fiがai個使われいるとする。
0がT個続く基底bの条件はfiの使われている個数の範囲が[ai / (t + 1) + 1, ai / t]となる物が1つ以上存在し、他は[0, ai / t]となっていることである。
後はこれをDPとかで計算してやれば良い。