第一眼就想到DP，然后想了N久就想不到可以不重算的DP 最后没办法了 先算出来 再去重。。
因为最多只有三个 对于三个来说有三种组合情况 x+y+z， x*y*z， x*y+z 那要么 x,y,z都不同 要么 有两个相同 要么有三个相同 对都不同情况我的DP结果会重复两次 对于有两个相同的会重复一次 统计出都相同的 两个相同的 最后减掉。。有点乱 不过A了
先预处理 时间差不多4S多 再O（1）询问
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
#define mod 1000000007
int dp[][][],prim[],o[];
int p1[][],p2[][],p3[][];
int num;
void init()
{
int i,j;
o[] = ;
o[] = ;
for(i = ; i <= ; i ++)
{
if(!o[i])
{
for(j = i+i; j <= ; j += i)
{
o[j] = ;
}
}
}
num = ;
for(i = ; i <= ; i ++)
{
if(!o[i])
prim[num++] = i;
}
for(i = ; i < num ; i++)
{
dp[][][prim[i]] = ;
dp[][][prim[i]] = ;
dp[][][prim[i]] = ;
}
for(i = ; i < num ; i++)
{
for(j = prim[i] ; j <= ; j++)
{
int k = j-prim[i];
if(!o[k]&&k>=prim[i])
dp[][][j] = (dp[][][j]+dp[][][k])%mod;
if(j%prim[i]==)
{
int k = j/prim[i];
if(k>=prim[i])
{
dp[][][j] = (dp[][][j]+dp[][][k])%mod;
dp[][][j] = dp[][][j];
}
}
}
}
for(i = ; i < num ; i++)
{
for(j = prim[i] ; j <= ; j++)
{
if(j%prim[i]==)
dp[][][j] = (dp[][][j]+dp[][][j/prim[i]])%mod;
dp[][][j] = (dp[][][j-prim[i]]+dp[][][j])%mod;
dp[][][j] = (dp[][][j]+dp[][][j-prim[i]])%mod;
}
}
for(i = ; i < num ; i++)
{
LL s = (LL)prim[i]*(LL)prim[i]*(LL)prim[i];
LL ss = prim[i]*;
if(ss<=)
p2[][ss] = (p2[][ss]+)%mod;
if(s<=)
p1[][s] = (p1[][s]+)%mod;
for(j = ; j < num ; j++)
{
if(j==i)
continue;
LL s = (LL)prim[i]*(LL)prim[i]*(LL)prim[j];
if(s<=)
p1[][s] = (p1[][s]+)%mod;
else
break;
}
for(j = ; j < num ; j++)
{
if(j==i)
continue;
LL ss = (LL)prim[i]*+prim[j];
if(ss<=)
p2[][ss] = (p2[][ss]+)%mod;
else
break;
}
}
}
int main()
{
int x;
init();
while(scanf("%d",&x)!=EOF)
{
LL s = (dp[][][x]+dp[][][x]+dp[][][x]+dp[][][x])%mod;
s = (s+(dp[][][x]-(p1[][x]+p1[][x]*))/+p1[][x]+p1[][x])%mod;
s = (s+(dp[][][x]-(p2[][x]+p2[][x]*))/+p2[][x]+p2[][x])%mod;
if(s<)
s+=mod;
printf("%lld\n",s);
}
return ;
}