制杖题
题目描述
求不大于 $m$ 的、质因数集与给定质数集有交集的自然数之和。
输入输出格式
输入格式
第一行，两个整数 $n, m$。
第二行，$n$ 个整数，表示质数集内的元素 $p_i$。
输出格式
一个整数，表示答案，对 $376544743$ 取模。
输入输出样例
输入样例 #1
2 15
3 5输出样例 #1
60说明
样例解释：所有符合条件的数为 $3,5,6,9,10,12,15$，其和为 $60$。
| 测试点编号 | 规模 |
|:-:|:-:|
| $1 \sim 3$ | $n m \le {10}^7$ |
| $4 \sim 5$ | $n \le 2$，$m \le {10}^9$ |
| $6 \sim 7$ | $n \le 20$，$m \le {10}^8$ |
| $8 \sim 10$ | $n \le 20$，$m \le {10}^9$ |
对于 $100 \%$ 的数据，$1 \le n \le 30$，$1 \le m \le {10}^9$。