Comet OJ

C1364 [Contest #9]【XR-3】Unknown Mother-Goose

内存限制：256 MB 时间限制：2000 ms

题目描述

小 X 得到了一个正整数 $n$ 和一个正整数集合 $S$，他想知道有多少个正整数 $x$ 满足以下所有条件：

  • $3 \le x \le n$
  • 存在 $a \in S, x \equiv 0 \mod a$
  • 存在 $b \in S,x-1 \equiv 0 \mod b$
  • 存在 $c \in S,x-2 \equiv 0 \mod c$

请你帮小 X 求出来。

输入格式

第一行两个正整数 $n,|S|$，表示你得到的 $n$ 和正整数集合 $S$ 的大小。

第二行 $|S|$ 个正整数，表示正整数集合 $S$ 中的元素。

数据范围：

  • $3 \le n \le 10^9$。
  • $3 \le |S| \le 20$。
  • 保证 $S$ 中所有元素均小于 $n$，不保证所有元素互不相同。

输出

一行一个整数，表示答案。

样例

样例输入 1

10 3
2 4 5

样例输出 1

1

样例输入 2

100000 6
14 47 31 233 666 59

样例输出 2

91

提示

【样例 $1$ 说明】

只有当 $x = 6$ 时：

  • $x \equiv 0 \mod 2$
  • $x \equiv 1 \mod 5$
  • $x \equiv 2 \mod 4$

满足条件。