eval'N,P='+gets.split*?,
a=[x=0]*-~N
2.upto(N){|i|x+=(1-P)**a[j=i]
a[j]+=1until N<j+=i}
p x