← 返回题目列表

AtCoder · abc317_f

I. 尼姆

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).

约束

  • 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