F - Nim Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 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 を表す。
ビット単位 xor とは 非負整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。
  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 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) のときの 4 通りが条件を満たします。

入力例 2

1000000000000000000 1 1 1

出力例 2

426724011

入力例 3

31415926535897932 3 8 4

出力例 3

759934997

Score : 500 points

Problem Statement

You are given integers N,A_1,A_2,A_3. Find the number, modulo 998244353, of triples of positive integers (X_1,X_2,X_3) that satisfy all of the following three conditions.

  • 1\leq X_i \leq N for every i.
  • X_i is a multiple of A_i for every i.
  • (X_1 \oplus X_2) \oplus X_3 = 0, where \oplus denotes bitwise xor.
What is bitwise xor? The bitwise xor of non-negative integers A and B, A \oplus B, is defined as follows.
  • When A \oplus B is written in binary, the 2^ks place (k \geq 0) is 1 if exactly one of the 2^ks places of A and B is 1, and 0 otherwise.
For instance, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110).

Constraints

  • 1 \leq N \leq 10^{18}
  • 1 \leq A_i \leq 10
  • All input values are integers.

Input

The Input is given from Standard Input in the following format:

N A_1 A_2 A_3

Output

Print the answer.

Sample Input 1

13 2 3 5

Sample Output 1

4

Four triples (X_1,X_2,X_3) satisfy the conditions: (6,3,5),(6,12,10),(12,6,10),(12,9,5).

Sample Input 2

1000000000000000000 1 1 1

Sample Output 2

426724011

Sample Input 3

31415926535897932 3 8 4

Sample Output 3

759934997