分数: 500 点
问题陈述
给你整数 N,A_1,A_2,A_3。求模数 998244353,正整数三元组 (X_1,X_2,X_3) 满足以下三个条件。
- 1\leq X_i \leq N 对于每个 i.
- X_i 是的倍数 A_i 对于每个 i.
- (X_1 \oplus X_2) \oplus X_3 = 0,其中 \oplus 表示按位异或。
什么是按位异或?
非负整数的按位异或 A 和 B, A \oplus B定义如下。- 当 A \oplus B 以二进制形式写入, 2^k的地方 (k \geq 0)是 1 如果恰好是其中之一 2^k的地方 A 和 B is 1,和 0 否则。
约束
- 1 \leq N \leq 10^{18}
- 1 \leq A_i \leq 10
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 A_3
输出
打印答案。
示例输入 1
13 2 3 5
示例输出 1
4
四个三元组 (X_1,X_2,X_3) 满足条件: (6,3,5),(6,12,10),(12,6,10),(12,9,5).
示例输入 2
1000000000000000000 1 1 1
示例输出 2
426724011
示例输入 3
31415926535897932 3 8 4
示例输出 3
759934997