#P11417. [2025安徽省队集训]吟游诗人

[2025安徽省队集训]吟游诗人

题目描述

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

输入格式

第一行两个正整数 n,m n, m 。 第二行 n n 个正整数,表示 a1,a2,⋯ ,an a_1, a_2, \cdots, a_n 。 第三行 m m 个正整数,表示 b1,b2,⋯ ,bm b_1, b_2, \cdots, b_m 。

输出格式

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

样例 1 输入

6 3 8 21 30 22 26 28 8 1 6

样例 1 输出

4

数据规模与约定

对于所有 10 10 个测试点,有 1≤n,ai,bi≤106 1 \leq n, a_i, b_i \leq 10^6 ,1≤m≤min⁡(n,17) 1 \leq m \leq \min(n, 17) ,ai a_i 互不相同;

对于测试点 1∼2 1 \sim 2 ,1≤n,ai,bi≤10 1 \leq n, a_i, b_i \leq 10 ;

对于测试点 3∼4 3 \sim 4 ,1≤n,ai≤30 1 \leq n, a_i \leq 30 ;

对于测试点 5∼7 5 \sim 7 ,1≤n≤1000 1 \leq n \leq 1000 ;

对于测试点 8 8 ,1≤m≤12 1 \leq m \leq 12 ;

对于测试点 9 9 ,1≤m≤14 1 \leq m \leq 14 ; 对于测试点 10 10 ,无特殊限制。