题目描述

AtCoder 国には $A_1$ 円玉、$A_2$ 円玉、$A_3$ 円玉、$\dots$ 、$A_N$ 円玉の $N$ 種類のコインがあります。
ここで $A_1\ =\ 1$ であり、$1\ \le\ i\ \lt\ N$ を満たす全ての整数 $i$ について、 $A_i\ \lt\ A_{i\ +\ 1}$ かつ $A_{i\ +\ 1}$ は $A_i$ の倍数です。

この国のある店で、犬のルンルンは $X$ 円の商品を購入するために店員に $y\ (\ge\ X)$ 円を渡し、店員はお釣りとして $y\ -\ X$ 円を返しました。(お釣りが $0$ 円の可能性もあります)
このとき、ルンルンも店員もその金額をちょうど渡すのに必要な最小の枚数のコインで受け渡しを行いました。
また、ルンルンが店員に渡したコインのいずれかと同じ種類のコインが店員から返されることはありませんでした。

$X$ が与えられるので、$y$ として考えられる値が何通りあるかを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $ A_1\ \hspace{7pt}\ A_2\ \hspace{7pt}\ A_3\ \hspace{5pt}\ \dots\ \hspace{5pt}\ A_N $

输出格式

$y$ として考えられる値が何通りあるかを出力せよ。

题目大意

有 $N$ 种硬币，面值分别为 $A_1,A_2,A_3 \dots A_N$ 元，满足 $A_1=1$，且对于所有 $1 \le i < N$，有 $A_i<A_{i+1}$ 且 $A_i|A_{i+1}$ 。

lunlun 用 $y(\ge X)$ 元 买了一件 $X$ 元的商品，收到了 $y-X$ 的找零。lunlun 和收银员都用了最少数量的硬币来付钱。特殊地，收银员没有和 lunlun 用相同种类的硬币。

给出 $X$，求 $y$ 有多少种可能。

3 9
1 5 10

3

5 198
1 5 10 50 100

5

4 44
1 4 20 100

4

9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

21

提示

制約

• $1\ \le\ N\ \le\ 50$
• $ 1\ =\ A_1\ \lt\ A_2\ \lt\ A_3\ \lt\ \dots\ \lt\ A_N\ \le\ 10^{15} $
• $A_{i\ +\ 1}$ は $A_i$ の倍数 $(1\ \le\ i\ \lt\ N)$
• $1\ \le\ X\ \le\ 10^{15}$
• 入力はすべて整数

Sample Explanation 1

$y$ として考えられる値は $9,\ 10,\ 14$ です。 例えば、 $y\ =\ 14$ のときルンルンは $10$ 円玉 $1$ 枚と $1$ 円玉 $4$ 枚を渡し、店員は $5$ 円玉 $1$ 枚でお釣りを返します。 このとき、ルンルンが渡したどの種類のコインも店員は返していないので条件を満たします。

Sample Explanation 2

$y$ として考えられる値は $198,\ 200,\ 203,\ 208,\ 248$ です。

Sample Explanation 3

$y$ として考えられる値は $44,\ 60,\ 100,\ 104$ です。