G - Balls and Boxes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

正整数 A, B, C, N が与えられます。
問題 1 および問題 2 をそれぞれ解いてください。(問題 1 と問題 2 で異なる箇所は太字で表記しています)

問題 1

N 個のボールがあります。ボール同士は区別できません。 また、箱 1、箱 2、箱 3 があります。
次の条件を満たすように箱に全てのボールを入れる方法の個数を 998244353 で割った余りを求めてください。

  • 箱 1 に入っているボールの個数は A の倍数である。
  • 箱 2 に入っているボールの個数は B の倍数である。
  • 箱 3 に入っているボールの個数は C の倍数である。

ただし、2 つのボールを入れる方法は、入っているボールの個数が 2 つの方法の間で異なる箱が存在する時に 別々に数えます。

問題 2

1 から N までの番号のついた N 個のボールがあります。ボール同士は区別できます。 また、箱 1、箱 2、箱 3 があります。
次の条件を満たすように箱に全てのボールを入れる方法の個数を 998244353 で割った余りを求めてください。

  • 箱 1 に入っているボールの個数は A の倍数である。
  • 箱 2 に入っているボールの個数は B の倍数である。
  • 箱 3 に入っているボールの個数は C の倍数である。

ただし、2 つのボールを入れる方法は、入っている箱が 2 つの方法の間で異なるボールが存在する時に 別々に数えます。

制約

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq A \leq 3 \times 10^5
  • 1 \leq B \leq 3 \times 10^5
  • 1 \leq C \leq 3 \times 10^5
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N A B C

出力

2 行出力せよ。i 行目には問題 i への答えを出力せよ。

入力例 1

3 1 2 3

出力例 1

3
5

問題 1 において条件を満たすボールの入れ方は次の 3 通りです。

  • 箱 1 に 3 個のボールを入れる。
  • 箱 1 に 1 個、箱 2 に 2 個のボールを入れる。
  • 箱 3 に 3 個のボールを入れる。

問題 2 において条件を満たすボールの入れ方は次の 5 通りです。

  • 箱 1 にボール 1,2,3 を入れる。
  • 箱 1 にボール 1 を、箱 2 にボール 2,3 を入れる。
  • 箱 1 にボール 2 を、箱 2 にボール 1,3 を入れる。
  • 箱 1 にボール 3 を、箱 2 にボール 1,2 を入れる。
  • 箱 3 にボール 1,2,3 を入れる。

入力例 2

1234 56 7 89

出力例 2

15
535248725

入力例 3

300000 6 490 420

出力例 3

73339
760083042

入力例 4

12345 67 89 123456

出力例 4

2
150951502

Score : 575 points

Problem Statement

You are given positive integers A, B, C, N.
Solve Problems 1 and 2. (The differences between the problems are indicated in bold.)

Problem 1

There are N balls. The balls are indistinguishable from each other. Also, there are boxes 1, 2, and 3.
Find the number, modulo 998244353, of ways to put all balls into the boxes satisfying the following conditions.

  • The number of balls in box 1 is a multiple of A.
  • The number of balls in box 2 is a multiple of B.
  • The number of balls in box 3 is a multiple of C.

Here, two ways of putting balls are counted separately when there exists a box where the number of balls differs between the two ways.

Problem 2

There are N balls numbered from 1 to N. The balls are distinguishable from each other. Also, there are boxes 1, 2, and 3.
Find the number, modulo 998244353, of ways to put all balls into the boxes satisfying the following conditions.

  • The number of balls in box 1 is a multiple of A.
  • The number of balls in box 2 is a multiple of B.
  • The number of balls in box 3 is a multiple of C.

Here, two ways of putting balls are counted separately when there exists a ball whose box differs between the two ways.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq A \leq 3 \times 10^5
  • 1 \leq B \leq 3 \times 10^5
  • 1 \leq C \leq 3 \times 10^5
  • All input values are integers.

Input

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

N A B C

Output

Output two lines. On the i-th line, output the answer to Problem i.

Sample Input 1

3 1 2 3

Sample Output 1

3
5

In Problem 1, the ways of putting balls that satisfy the condition are the following three ways:

  • Put 3 balls in box 1.
  • Put 1 ball in box 1 and 2 balls in box 2.
  • Put 3 balls in box 3.

In Problem 2, the ways of putting balls that satisfy the condition are the following five ways:

  • Put balls 1,2,3 in box 1.
  • Put ball 1 in box 1 and balls 2,3 in box 2.
  • Put ball 2 in box 1 and balls 1,3 in box 2.
  • Put ball 3 in box 1 and balls 1,2 in box 2.
  • Put balls 1,2,3 in box 3.

Sample Input 2

1234 56 7 89

Sample Output 2

15
535248725

Sample Input 3

300000 6 490 420

Sample Output 3

73339
760083042

Sample Input 4

12345 67 89 123456

Sample Output 4

2
150951502