墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。

输出一个整数，表示有多少b可以使等式存在非负整数解。

对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue>//by NeighThorn#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const int maxn=12+5,maxm=500000+5;int n,be,a[maxn],vis[maxm];long long BMin,BMax,dis[maxm];queue<int> q;inline void spfa(void){	for(int i=0;i<a[be];i++) dis[i]=inf;	dis[0]=0;vis[0]=1;q.push(0);	while(!q.empty()){		int top=q.front();q.pop();vis[top]=0;		for(int i=be,x;i<=n;i++){			x=(top+a[i])%a[be];			if(dis[x]>dis[top]+a[i]){				dis[x]=dis[top]+a[i];				if(!vis[x])					q.push(x),vis[x]=1;			}		}	}}inline long long calc(long long x){	long long ans=0;	for(int i=0;i<a[be];i++)		if(dis[i]<=x) ans+=(x-dis[i])/a[be]+1;	return ans;}signed main(void){#ifndef ONLINE_JUDGE	freopen("equation9.in","r",stdin);	freopen("out.txt","w",stdout);#endif	scanf("%d%lld%lld",&n,&BMin,&BMax);	for(int i=1;i<=n;i++) scanf("%d",&a[i]);be=1;	sort(a+1,a+n+1);if(!a[n]) {puts("0");return 0;}	while(a[be]==0) be++;spfa();	printf("%lld\n",calc(BMax)-calc(BMin-1));	return 0;}