灯的颜色变换与红灯个数期望问题

题目描述

有 $n$ 盏灯，编号从 1 到 $n$。每盏灯有四种颜色：红、绿、蓝、黄，初始时所有灯的颜色均为红色。

现有 $m$ 个操作，第 $i$ 个操作用整数 $x_i$ 描述，执行该操作时，会对所有标号为 $x_i$ 倍数的灯进行一次颜色变换。

颜色变换遵循固定循环规则：红色 → 绿色 → 蓝色 → 黄色 → 红色（即每次操作切换到下一种颜色，循环往复）。

拉灯的人会等概率随机选取若干个操作（可选取 0 个，即不执行任何操作），然后执行选中的所有操作（操作顺序不影响最终结果）。请你计算最终红灯个数的期望值，答案需对 998244353 取模。

输入格式

从标准输入读入数据：

• 第一行包含两个正整数 $n$ 和 $m$，分别表示灯的数量和操作的数量。
• 第二行包含 $m$ 个正整数 $x_1, x_2, \dots, x_m$，分别描述每个操作对应的 $x_i$。

输出格式

输出到标准输出：

• 一行一个整数，表示最终红灯个数的期望值对 998244353 取模后的结果。

样例

样例 1

输入

1 4
1 1 1 1

输出

873463809

样例 2

输入

3 2
2 1

输出

748683266

数据范围与提示

通用数据限制

• $1 \leq x_i \leq n \leq 10^9$
• $1 \leq m \leq 20$

子任务划分

提示：由于 $n$ 可能极大，无法枚举每盏灯，需利用期望的线性性质和集合运算优化计算；$m$ 较小（≤20），可通过状态压缩或子集枚举处理操作组合。