// https://yukicoder.me/submissions/717274 #pragma GCC optimize("Ofast") #pragma GCC target("avx2") char*mmap(); #define rd_skip() while(*rp++>=48) #define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;} #define wt(v) {long _z=v;do*--wp=_z%10+48;while(_z/=10);} long gcd(long a,long b){ if(a==0||b==0){ return a+b; } long x=__builtin_ctzl(a); long y=__builtin_ctzl(b); a>>=x; b>>=y; long c; while(c=a-b){ c>>=__builtin_ctzl(c); if(c<0){ b=-c; }else{ a=c; } } return a<<(x<=y?x:y); } #define H_BITS 13 #define H_LEN (1<>H_BITS)&H_MASK; while(h[l]!=0&&h[l]!=v){ l=l+1&H_MASK; } h[l]=v; return l; } int divn; int divs[2000]; int divh[2000]; int dp[H_LEN]; #define MD 1000000007 main(){ char*rp=mmap(0l,1l<<25,1,2,0,0ll); rd_skip(); rd(k); for(long i=1;i*i<=k;++i){ if(k%i==0){ divs[divn++]=i; } } for(long j=divn-(divs[divn-1]*divs[divn-1]==k);--j>=0;){ divs[divn++]=k/divs[j]; } dp[geth(1)]=1; while(*rp){ rd(a); a=gcd(k,a); for(long j=divn;--j>=0;){ long c=divs[j]; long ch=geth(c); long b=gcd(k,a*c); long bh=geth(b); long v=dp[bh]+dp[ch]; v-=v