题目描述

数字王国的吟游诗人小可可吟诵出了 $n$ 个意象，每个意象可以由一个正整数 $a_i$ 刻画，意象之间两两不同。 一首诗可视作一个长为 $m$ 的、包含若干不同意象的序列，并且诗中的第 $i$ 个意象对应的正整数是 $b_i$ 的倍数。 小可可想知道，一共可以有多少不同的诗可以从他吟诵出的 $n$ 个意象里写出，由于答案可能很大，只需输出其对 $10^9 + 7$ 取模后的结果。.

输入格式

第一行两个正整数 $n, m$。 第二行 $n$ 个正整数，表示 $a_1, a_2, \cdots, a_n$。 第三行 $m$ 个正整数，表示 $b_1, b_2, \cdots, b_m$。

输出格式

一个正整数，表示答案取模后的结果。

样例 1 输入

6 3 8 21 30 22 26 28 8 1 6

样例 1 输出

4

数据规模与约定

对于所有 $10$ 个测试点，有 $1 \leq n, a_i, b_i \leq 10^6$，$1 \leq m \leq \min(n, 17)$，$a_i$ 互不相同；

对于测试点 $1 \sim 2$，$1 \leq n, a_i, b_i \leq 10$；

对于测试点 $3 \sim 4$，$1 \leq n, a_i \leq 30$；

对于测试点 $5 \sim 7$，$1 \leq n \leq 1000$；

对于测试点 $8$，$1 \leq m \leq 12$；

对于测试点 $9$，$1 \leq m \leq 14$； 对于测试点 $10$，无特殊限制。