Description:


墨墨突然对等式很感兴趣,他正在研究 \(a_1\cdot x_1+a_2\cdot x_2+\cdots +a_n\cdot x_n=B\) 存在非负整数解的条件,他要求你编写一个程序,给定 \(N\) 、数列 \(a_n\) 、以及 \(B\) 的取值范围,求出有多少B可以使等式存在非负整数解。

Input:


输入的第一行包含3个正整数,分别表示 \(N, BMin, BMax\) 分别表示数列的长度、 \(B\) 的下界、 \(B\) 的上界。输入的第二行包含 \(N\) 个整数,即数列 \(a_n\) 的值。

Output:


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

Sample Input:


Sample Output:


HINT:


对于100%的数据, \(N\le 12, 0\le ai\le 5\times 10^5, 1\le BMin\le BMax\le 10^{12}\)

题解:


一开始就不是往最短路想的.....

我们考虑在模任意一个 \(a_i\) (设为 \(a_0\) )的意义下,共有 \(a_0\) 个同余类,可以分别计数。

对于一个同余类 \(k\cdot a_0 + x (0\le x \lt a_0)\) ,我们只需要算出最小的 \(k\) 便可以在 \([L, R]\) 中计数了。

可以考虑把每个 \(x\) 看作一个点,除去 \(a_0\) 以外的每一个 \(a_i\) 都去为每一个点加边。

理解了其实很简单。