题目描述

给定整数 $N, A_1, A_2, A_3$。请计算满足以下 $3$ 个条件的正整数三元组 $(X_1, X_2, X_3)$ 的个数，并将答案对 $998244353$ 取模。

• 对所有 $i$，都有 $1 \leq X_i \leq N$。
• 对所有 $i$，$X_i$ 是 $A_i$ 的倍数。
• $(X_1 \oplus X_2) \oplus X_3 = 0$。其中，$\oplus$ 表示按位异或运算。

按位异或（xor）是这样定义的：对于非负整数 $A, B$，$A \oplus B$ 的二进制表示中每一位 $2^k$（$k \geq 0$）的值为：如果 $A, B$ 的该位中恰有一个为 $1$，则该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $A_3$

输出格式

请输出答案。

样例 1

输入

13 2 3 5

输出

4

样例 2

输入

1000000000000000000 1 1 1

输出

426724011

样例 3

输入

31415926535897932 3 8 4

输出

759934997

说明/提示

限制条件

• $1 \leq N \leq 10^{18}$
• $1 \leq A_i \leq 10$
• 输入均为整数

样例解释 1

当 $(X_1, X_2, X_3)$ 分别为 $(6,3,5), (6,12,10), (12,6,10), (12,9,5)$ 时，共有 $4$ 种满足条件的方案。

由 ChatGPT 4.1 翻译