AtCoder Beginner Contest 473

A - Second Half Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。ここで、 N は偶数です。
A の後半部分の総和、つまり、 A_{(N/2)+1},A_{(N/2)+2},\dots,A_{N} の総和を求めてください。

制約

入力は全て整数
N は 2 \le N \le 100 を満たす偶数
1 \le A_i \le 100

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

8
1 3 7 8 4 2 5 6

出力例 1

数列 A の長さは N=8 であり、求めるべきは A_5,A_6,A_7,A_8 の総和です。
A_5+A_6+A_7+A_8 = 4+2+5+6=17 なので、 17 と出力してください。

入力例 2

2
1 100

出力例 2

入力例 3

10
31 41 59 26 53 58 97 93 23 84

出力例 3

Score : 100 points

Problem Statement

You are given an integer sequence of length N: A=(A_1,A_2,\dots,A_N). Here, N is even.
Find the sum of the latter half of A, that is, the sum of A_{(N/2)+1},A_{(N/2)+2},\dots,A_{N}.

Constraints

All input values are integers.
N is an even number satisfying 2 \le N \le 100.
1 \le A_i \le 100

Input

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

N
A_1 A_2 \dots A_N

Output

Output the answer.

Sample Input 1

8
1 3 7 8 4 2 5 6

Sample Output 1

The length of the sequence A is N=8, and you should find the sum of A_5,A_6,A_7,A_8.
Since A_5+A_6+A_7+A_8 = 4+2+5+6=17, output 17.

Sample Input 2

2
1 100

Sample Output 2

Sample Input 3

10
31 41 59 26 53 58 97 93 23 84

Sample Output 3

B - Old Maid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋くんは、現在 N 枚のカードを持っています。 i 番目 (1\le i\le N) のカードには整数 A _ i が書かれています。

高橋くんは、以下の操作を可能な限り繰り返します。

同じ整数が書かれている異なる 2 枚のカードを選び、それら 2 枚のカードを食べる。食べたカードは永久に取り除かれ、以降の操作で選ぶことはできない。

操作ができなくなったときに残っているカードに書かれている整数の合計を求めてください。

制約

1\le N\le100
1\le A _ i\le100\ (1\le i\le N)
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \cdots A _ N

出力

残ったカードに書かれている整数の合計を出力せよ。

入力例 1

8
2 7 1 8 2 8 1 8

出力例 1

例えば、高橋くんは以下のように操作を行います。

4 枚目のカードと 6 枚目のカードにはどちらも 8 が書かれているため、それらを選び、食べる。
1 枚目のカードと 5 枚目のカードにはどちらも 2 が書かれているため、それらを選び、食べる。
3 枚目のカードと 7 枚目のカードにはどちらも 1 が書かれているため、それらを選び、食べる。

よって、残ったカードに書かれている整数の合計は 7+8=15 です。

8 と書かれたカードは 3 枚あるので、これらのうちの 2 枚を食べると残った 1 枚は食べられないことに注意してください。

入力例 2

5
1 2 3 4 5

出力例 2

高橋くんが操作を一度も行えない場合もあります。

入力例 3

15
58 97 74 16 97 74 97 16 51 52 58 52 74 32 43

出力例 3

Score : 200 points

Problem Statement

Takahashi currently has N cards. The i-th (1\le i\le N) card has the integer A _ i written on it.

He repeats the following operation as many times as possible.

Choose two different cards with the same integer written on them, and eat those two cards. The eaten cards are permanently removed and cannot be chosen in subsequent operations.

Find the sum of the integers written on the cards that remain when the operation can no longer be performed.

Constraints

1\le N\le100
1\le A _ i\le100\ (1\le i\le N)
All input values are integers.

Input

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

N
A _ 1 A _ 2 \cdots A _ N

Output

Output the sum of the integers written on the remaining cards.

Sample Input 1

8
2 7 1 8 2 8 1 8

Sample Output 1

For example, Takahashi operates as follows.

The fourth card and sixth card both have 8 written on them, so he chooses them and eats them.
The first card and fifth card both have 2 written on them, so he chooses them and eats them.
The third card and seventh card both have 1 written on them, so he chooses them and eats them.

Thus, the sum of the integers written on the remaining cards is 7+8=15.

Note that there are three cards with 8 written on them, so once two of them are eaten, the remaining one cannot be eaten.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

It is possible that Takahashi cannot perform the operation even once.

Sample Input 3

15
58 97 74 16 97 74 97 16 51 52 58 52 74 32 43

Sample Output 3

C - Change Schools

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

現在 AtCoder 高校には K 個のクラスと N 人の生徒が存在し、i 人目 (1\le i\le N) の生徒は A _ i 番目のクラスに所属しています。

高橋くんは 9 月から AtCoder 高校に転入することになりました。高橋くんは、転入する際に K 個のクラスの中から好きなクラスを 1 つ選び、そのクラスに所属することができます。

高橋くんは、自分が所属しているクラスより多い人数が所属しているクラスがあるとき悲しみ、そうでないとき喜びます。

所属したときに高橋くんが喜ぶクラスがいくつあるか求めてください。

制約

1\le N\le2\times10 ^ 5
1\le K\le N
1\le A _ i\le K\ (1\le i\le N)
入力はすべて整数

入力

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

N K
A _ 1 A _ 2 \ldots A _ N

出力

条件を満たすクラスの個数を出力せよ。

入力例 1

8 5
3 3 5 5 4 4 3 2

出力例 1

例えば、高橋くんが 5 番目のクラスを選んで所属したとき、5 番目のクラスに所属している人数は 3 人となります。このとき、3 人より多い人数が所属しているクラスは存在しないため、高橋くんは喜びます。

一方、例えば高橋くんが 1 番目のクラスを選んで所属したとき、1 番目のクラスに所属している人数は 1 人となります。このとき、3 番目のクラスに所属している人数は 3 人なので、高橋くんは悲しみます。

3,4,5 番目のクラスを選んだとき、かつそのときに限り高橋くんは喜ぶので、3 を出力してください。

入力例 2

6 1
1 1 1 1 1 1

出力例 2

AtCoder 高校にクラスが 1 つしかない場合もあります。

入力例 3

14 8
6 1 5 3 8 4 3 4 3 5 1 2 5 1

出力例 3

Score : 300 points

Problem Statement

Currently, AtCoder High School has K classes and N students, and the i-th (1\le i\le N) student belongs to the A _ i-th class.

Takahashi is transferring to AtCoder High School in September. At that time, he can choose any one class among the K classes and belong to that class.

He will be sad if there is a class with more students belonging to it than the class he belongs to. Otherwise, he will be happy.

Find how many classes make him happy if he belongs to them.

Constraints

1\le N\le2\times10 ^ 5
1\le K\le N
1\le A _ i\le K\ (1\le i\le N)
All input values are integers.

Input

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

N K
A _ 1 A _ 2 \ldots A _ N

Output

Output the number of classes satisfying the condition.

Sample Input 1

8 5
3 3 5 5 4 4 3 2

Sample Output 1

For example, if Takahashi chooses the fifth class and belongs to it, the number of students belonging to the fifth class becomes 3. Then, he will be happy since there is no class with more than three students belonging to it.

On the other hand, for example, if he chooses the first class and belongs to it, the number of students belonging to the first class becomes 1. Then, he will be sad since three students belong to the third class.

He will be happy if and only if he chooses the third, fourth, or fifth class, so output 3.

Sample Input 2

6 1
1 1 1 1 1 1

Sample Output 2

It is possible that AtCoder High School has only one class.

Sample Input 3

14 8
6 1 5 3 8 4 3 4 3 5 1 2 5 1

Sample Output 3

D - Coefficient Stair

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

非負整数からなる長さ N の列 A=(A _ 1,A _ 2,\ldots,A _ N) であって、\displaystyle\sum _ {i=1} ^ Ni\times A _ i=K を満たすものを辞書順で小さいほうからすべて出力してください。

ここで、条件を満たす数列が 3\times10 ^ 5 個以下であるような入力のみが与えられます。

数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは，下記の 1. と 2. のどちらかが成り立つことを言います．ここで，|S|, |T| はそれぞれ S, T の長さを表します．

|S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})．
ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して，下記の 2 つがともに成り立つ．
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい．

制約

1\le N\le 10
1\le K\le 2\times10 ^ 5
条件を満たす数列は 3\times10 ^ 5 個以下
入力はすべて整数

入力

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

N K

出力

条件を満たす非負整数列が q 個あるとして、q 行にわたって出力せよ。それぞれの行には条件を満たす非負整数列の要素を空白を区切りとして順に出力せよ。どの数列についても、その数列より前に出力された数列はどれもその数列より辞書順で小さくなければならない。

入力例 1

3 8

出力例 1

例えば、列 (0,1,2) は 0\times1+1\times2+2\times3=0+2+6=8 となるため条件を満たします。条件を満たす列であってこれより辞書順で小さいものは存在しないため、1 行目には 0 1 2 を出力してください。

(0,1,2) とあわせて 10 個の列が条件を満たします。これらを辞書順で小さいほうから出力してください。

入力例 2

1 200000

出力例 2

入力例 3

8 9

出力例 3

0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 3 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 1 1 0 0 0 0
0 2 0 0 1 0 0 0
0 3 1 0 0 0 0 0
1 0 0 0 0 0 0 1
1 0 0 2 0 0 0 0
1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 2 0 0 0 0 0
1 2 0 1 0 0 0 0
1 4 0 0 0 0 0 0
2 0 0 0 0 0 1 0
2 0 1 1 0 0 0 0
2 1 0 0 1 0 0 0
2 2 1 0 0 0 0 0
3 0 0 0 0 1 0 0
3 0 2 0 0 0 0 0
3 1 0 1 0 0 0 0
3 3 0 0 0 0 0 0
4 0 0 0 1 0 0 0
4 1 1 0 0 0 0 0
5 0 0 1 0 0 0 0
5 2 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 1 0 0 0 0 0 0
9 0 0 0 0 0 0 0

Score : 400 points

Problem Statement

Output all length-N sequences A=(A _ 1,A _ 2,\ldots,A _ N) consisting of non-negative integers that satisfy \displaystyle\sum _ {i=1} ^ Ni\times A _ i=K, in lexicographic order from smallest to largest.

Here, you will only receive inputs such that the number of sequences satisfying the condition is at most 3\times10 ^ 5.

What is lexicographic order for sequences?

A sequence S = (S_1,S_2,\ldots,S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if either 1. or 2. below holds. Here, |S| and |T| denote the lengths of S and T, respectively.

|S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold.
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i is (numerically) smaller than T_i.

Constraints

1\le N\le 10
1\le K\le 2\times10 ^ 5
The number of sequences satisfying the condition is at most 3\times10 ^ 5.
All input values are integers.

Input

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

N K

Output

Let q be the number of sequences of non-negative integers satisfying the condition; output them over q lines. Each line should contain the elements of a sequence of non-negative integers satisfying the condition, in order, separated by spaces. For every sequence, all sequences outputed before it must be lexicographically smaller than it.

Sample Input 1

3 8

Sample Output 1

For example, for the sequence (0,1,2) we have 0\times1+1\times2+2\times3=0+2+6=8, so it satisfies the condition. There is no sequence satisfying the condition that is lexicographically smaller than this one, so output 0 1 2 on the first line.

Including (0,1,2), ten sequences satisfy the condition. Output these in lexicographic order from smallest to largest.

Sample Input 2

1 200000

Sample Output 2

Sample Input 3

8 9

Sample Output 3

0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 3 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 1 1 0 0 0 0
0 2 0 0 1 0 0 0
0 3 1 0 0 0 0 0
1 0 0 0 0 0 0 1
1 0 0 2 0 0 0 0
1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 2 0 0 0 0 0
1 2 0 1 0 0 0 0
1 4 0 0 0 0 0 0
2 0 0 0 0 0 1 0
2 0 1 1 0 0 0 0
2 1 0 0 1 0 0 0
2 2 1 0 0 0 0 0
3 0 0 0 0 1 0 0
3 0 2 0 0 0 0 0
3 1 0 1 0 0 0 0
3 3 0 0 0 0 0 0
4 0 0 0 1 0 0 0
4 1 1 0 0 0 0 0
5 0 0 1 0 0 0 0
5 2 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 1 0 0 0 0 0 0
9 0 0 0 0 0 0 0

E - K-Divisible Subarrays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

非負整数からなる長さ N の列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。

非負整数列からなる長さ 1 以上の列 S=(S _ 1,S _ 2,\ldots,S _ k) のスコアを、列 S _ i\ (1\le i\le k) のうち要素の総和が K で割り切れるものの個数として定めます。

A を 1 つ以上の連続する部分列に分割して得られる非負整数列の列に対するスコアの最大値を求めてください。ここで、長さ N の列 A を 1 つ以上の連続する部分列に分割するとは、整数からなる長さ 1 以上の列 l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N) をとり、以下のような k 個の列を作ることをいいます。

(A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k) （ここで、l _ {k+1}=N+1 とする。）

制約

1\le N\le2\times10 ^ 5
1\le K\le10 ^ 9
0\le A _ i\lt K
入力はすべて整数

入力

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

N K
A _ 1 A _ 2 \ldots A _ N

出力

答えを出力せよ。

入力例 1

6 10
6 8 2 2 6 4

出力例 1

例えば、A を (6),(8,2),(2),(6,4) のように 4 つの連続する部分列に分割することができます。 2 番目と 4 番目の列の要素の総和が 10 の倍数になるので、((6),(8,2),(2),(6,4)) のスコアは 2 です。

スコアが 3 以上になるように A を分割することはできないので、2 を出力してください。

入力例 2

8 1
0 0 0 0 0 0 0 0

出力例 2

入力例 3

30 8
5 0 4 2 7 3 2 3 2 4 0 1 4 0 4 1 7 5 2 5 0 3 6 6 2 3 2 2 4 2

出力例 3

Score : 450 points

Problem Statement

You are given a sequence of length N consisting of non-negative integers: A=(A _ 1,A _ 2,\ldots,A _ N) .

Define the score of a sequence of length 1 or more consisting of sequences of non-negative integers, S=(S _ 1,S _ 2,\ldots,S _ k), as the number of sequences S _ i\ (1\le i\le k) whose sum of elements is divisible by K.

Find the maximum possible score of a sequence of non-negative integer sequences obtained by dividing A into one or more contiguous subsequences. Here, dividing a sequence A of length N into one or more contiguous subsequences means choosing a sequence of integers l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N) of length 1 or more, and forming the following k sequences.

(A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k) (Here, let l _ {k+1}=N+1.)

Constraints

1\le N\le2\times10 ^ 5
1\le K\le10 ^ 9
0\le A _ i\lt K
All input values are integers.

Input

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

N K
A _ 1 A _ 2 \ldots A _ N

Output

Output the answer.

Sample Input 1

6 10
6 8 2 2 6 4

Sample Output 1

For example, A can be divided into four contiguous subsequences as (6),(8,2),(2),(6,4). The sums of the elements of the second and fourth sequences are multiples of 10, so the score of ((6),(8,2),(2),(6,4)) is 2.

A cannot be divided so that the score is 3 or more, so output 2.

Sample Input 2

8 1
0 0 0 0 0 0 0 0

Sample Output 2

Sample Input 3

30 8
5 0 4 2 7 3 2 3 2 4 0 1 4 0 4 1 7 5 2 5 0 3 6 6 2 3 2 2 4 2

Sample Output 3

F - A/AB Insertion

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

長さ N の A, B からなる文字列 S が与えられます。
以下のクエリを合計 Q 個処理してください。

1 i c

タイプ 1 : S の i 文字目を c に変更する。

2 l r

タイプ 2 :
文字列 T を、現在の文字列 S の l 文字目から r 文字目までを抜き出した文字列とする。
文字列 T が以下の操作で得られる文字列であれば Yes 、そうでなければ No と出力する。

空文字列から始め、以下の 2 つの操作を好きな順序で 0 回以上何回でも行う。

文字列の(先頭・末尾を含めた)任意の箇所を選択し、そこに A を挿入する。

文字列の(先頭・末尾を含めた)任意の箇所を選択し、そこに AB を挿入する。

制約

N は 1 \le N \le 5 \times 10^5 を満たす整数
S は A, B からなる長さ N の文字列
Q は 1 \le Q \le 2 \times 10^5 を満たす整数
与えられるクエリはタイプ 1,2 のいずれかである
タイプ 1 のクエリは以下の制約を満たす
- i は 1 \le i \le N を満たす整数
- c は A, B のいずれか
タイプ 2 のクエリは以下の制約を満たす
- l,r は 1 \le l \le r \le N を満たす整数

入力

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

N
S
Q
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

但し、 {\rm Query}_i は i 個目のクエリを表し、クエリの入力は問題文中の形式に従う。

出力

タイプ 2 のクエリが入力されるごとに、答えを 1 行に出力せよ。

入力例 1

10
AABBAABABB
6
2 1 10
1 5 B
2 1 10
2 6 8
1 3 A
2 1 10

出力例 1

Yes
No
Yes
Yes

この入力には 6 個のクエリが含まれます。

最初、 S= AABBAABABB です。
1 つ目のクエリについて、 S の 1 文字目から 10 文字目までを抜き出した T= AABBAABABB は以下の手順を踏むことで得ることができるため、 Yes と出力します。
- 空文字列から始める。
- 空文字列の先頭に AB を挿入し、文字列が AB となる。
- AB の 1 文字目の直後に AB を挿入し、文字列が AABB となる。
- AABB の末尾に AB を挿入し、文字列が AABBAB となる。
- AABBAB の 5 文字目の直後に AB を挿入し、文字列が AABBAABB となる。
- AABBAABB の 7 文字目の直後に AB を挿入し、文字列が AABBAABABB となる。
2 つ目のクエリについて、 S の 5 文字目を B に変更します。その結果、 S= AABBBABABB となります。
3 つ目のクエリについて、 S の 1 文字目から 10 文字目までを抜き出した T= AABBBABABB は問題文中の操作では得られないため、 No と出力します。
4 つ目のクエリについて、 S の 6 文字目から 8 文字目までを抜き出した T= ABA は問題文中の操作で得ることができるため、 Yes と出力します。
5 つ目のクエリについて、 S の 3 文字目を A に変更します。その結果、 S= AAABBABABB となります。
6 つ目のクエリについて、 S の 1 文字目から 10 文字目までを抜き出した T= AAABBABABB は問題文中の操作で得ることができるため、 Yes と出力します。

Score : 525 points

Problem Statement

You are given a string S of length N consisting of A and B.
Process a total of Q queries of the following types.

1 i c

Type 1: Change the i-th character of S to c.

2 l r

Type 2:
Let string T be the string obtained by extracting the l-th through r-th characters of the current string S.
If it is possible to obtain string T by the following operation, output Yes; otherwise, output No.

Starting from the empty string, perform the following two operations any number of times, possibly zero, in any order.

Choose any position in the string (possibly the beginning or the end) and insert A there.

Choose any position in the string (possibly the beginning or the end) and insert AB there.

Constraints

N is an integer satisfying 1 \le N \le 5 \times 10^5.
S is a string of length N consisting of A and B.
Q is an integer satisfying 1 \le Q \le 2 \times 10^5.
Each given query is of type 1 or 2.
Queries of type 1 satisfy the following constraints:
- i is an integer satisfying 1 \le i \le N, and
- c is A or B.
Queries of type 2 satisfy the following constraints:
- l and r are integers satisfying 1 \le l \le r \le N.

Input

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

N
S
Q
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

Here, {\rm Query}_i represents the i-th query, and the input format for a query follows the format described in the problem statement.

Output

Each time a query of type 2 is given, output the answer on one line.

Sample Input 1

10
AABBAABABB
6
2 1 10
1 5 B
2 1 10
2 6 8
1 3 A
2 1 10

Sample Output 1

Yes
No
Yes
Yes

This input contains six queries.

Initially, S= AABBAABABB.
For the 1-st query, T= AABBAABABB, obtained by extracting the 1-st through 10-th characters of S, can be obtained by the following steps, so output Yes.
- Start from the empty string.
- Insert AB at the beginning of the empty string, making the string AB.
- Insert AB right after the 1-st character of AB, making the string AABB.
- Insert AB at the end of AABB, making the string AABBAB.
- Insert AB right after the 5-th character of AABBAB, making the string AABBAABB.
- Insert AB right after the 7-th character of AABBAABB, making the string AABBAABABB.
For the 2-nd query, change the 5-th character of S to B. As a result, S= AABBBABABB.
For the 3-rd query, T= AABBBABABB, obtained by extracting the 1-st through 10-th characters of S, cannot be obtained by the operation described in the problem statement, so output No.
For the 4-th query, T= ABA, obtained by extracting the 6-th through 8-th characters of S, can be obtained by the operation described in the problem statement, so output Yes.
For the 5-th query, change the 3-rd character of S to A. As a result, S= AAABBABABB.
For the 6-th query, T= AAABBABABB, obtained by extracting the 1-st through 10-th characters of S, can be obtained by the operation described in the problem statement, so output Yes.

G - Wipeout

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

表に整数 1,2,\dots,N が書かれたカードが 1 枚ずつ、計 N 枚のカードが裏返しで一列に並べられています。
さらに、これらのカードの並び順は N! 通りの中から一様ランダムに定められます。
また、あなたは表に整数 1,2,\dots,N が書かれたカードが 1 枚ずつあること、カードが一様ランダムに並べられたことを知っていますが、カードの表に書かれている整数に関する情報はこれ以上持っていません。

あなたは以下のゲームを行います。

最初、変数 x=1 とする。
x \le N である限り、以下の操作を繰り返す。 1 回の操作は以下の 3 つの手順からなる。
- カードを 1 枚指定して、それを表に向ける。
- カードに書かれた整数が x ならそのカードを食べ、 x に 1 加算する。
- そうでないなら、そのカードを裏に向ける。あなたはそのカードに書かれた整数を永久に記憶しておくことができる。

あなたは常に全てのカードを食べ終わるまでの操作の総数の期待値が最小となるように行動します。
この場合、操作の総数が K 回となる確率はいくらでしょうか？ \text{mod }{998244353} で求めてください。

確率 \text{mod }{998244353} の定義

求める確率は必ず有理数になることが証明できます。また、この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることが証明できます。よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。この R を答えてください。

制約

入力は全て整数
1 \le N \le 5 \times 10^5
N \le K \le 10^9

入力

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

N K

出力

答えを出力せよ。

入力例 1

3 4

出力例 1

499122177

この入力について N=3 であり、各カードを並んでいる順に a,b,c と呼ぶことにします。
操作の総数の期待値が最小となるように行動するあなたの行動の一例を以下に示します。

まず、 a を表に向けます。
a に 1 が書かれていた場合、そのカードを食べます。
- 次に、 b を表に向けます。
- b に 2 が書かれていた場合、そのカードを食べます。
  - 次に c を表に向け、そこには必ず 3 が書かれているのでそれを食べます。この場合、操作 3 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
- b に 3 が書かれていた場合、そのカードを裏に向けます。
  - 次に c を表に向け、そこには必ず 2 が書かれているのでそれを食べます。その後、 b を表に向け、食べます。この場合、操作 4 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
a に 2 が書かれていた場合、そのカードを裏に向けます。
- 次に、 b を表に向けます。
- b に 1 が書かれていた場合、そのカードを食べます。
  - 次に a を表に向け、食べます。次に c を表に向け、そこには必ず 3 が書かれているのでそれを食べます。この場合、操作 4 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
- b に 3 が書かれていた場合、そのカードを裏に向けます。
  - この時点で、どのカードにどの整数が書かれているかが全てのカードについて判明しました。なので、 3 回操作を行い全てのカードを番号順に食べます。この場合、操作 5 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
a に 3 が書かれていた場合、そのカードを裏に向けます。
- 次に、 b を表に向けます。
- b に 1 が書かれていた場合、そのカードを食べます。
  - 次に c を表に向け、そこには必ず 2 が書かれているのでそれを食べます。その後、 a を表に向け、食べます。この場合、操作 4 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。
- b に 2 が書かれていた場合、そのカードを裏に向けます。
  - この時点で、どのカードにどの整数が書かれているかが全てのカードについて判明しました。なので、 3 回操作を行い全てのカードを番号順に食べます。この場合、操作 5 回で全てのカードを食べ終わり、このようになる確率は 1/6 です。

全てを統合すると、操作の総数が 3 回となる確率は 1/6 、 4 回となる確率は 1/2 、 5 回となる確率は 1/3 です。
本サンプルに対しては、 1/2 を \text{mod }{998244353} で表現した 499122177 を出力します。

入力例 2

3 6

出力例 2

入力例 3

500000 777777

出力例 3

251612105

Score : 600 points

Problem Statement

There are N cards arranged face down in a row, each with one of the integers 1,2,\dots,N written on its face.
The order of these cards is determined uniformly at random from the N! possible orders.
You know that there is exactly one card with each of the integers 1,2,\dots,N written on its face and that the cards were arranged uniformly at random, but you have no other information about the integers written on the faces of the cards.

You play the following game.

Initially, let the variable x=1.
As long as x \le N, repeat the following operation. One operation consists of the following three steps.
- Specify one card and turn it face up.
- If the integer written on the card is x, eat that card and add 1 to x.
- Otherwise, turn that card face down. You can permanently remember the integer written on that card.

You always act so that the expected value of the total number of operations until all cards have been eaten is minimized.
In this case, what is the probability that the total number of operations is K? Find it modulo 998244353.

Definition of probability modulo 998244353

It can be proved that the sought probability is always a rational number. Also, under the constraints of this problem, it can be proved that when the rational number to be found is expressed as an irreducible fraction \frac{P}{Q}, we have Q {{}\not\equiv{}} 0 \pmod{998244353}. Therefore, there is a unique integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Output this R.

Constraints

All input values are integers.
1 \le N \le 5 \times 10^5
N \le K \le 10^9

Input

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

N K

Output

Output the answer.

Sample Input 1

3 4

Sample Output 1

499122177

For this input, N=3. Let us call the cards a,b,c in the order they are arranged.
Below is an example of your actions when acting so that the expected value of the total number of operations is minimized.

First, turn a face up.
If 1 is written on a, eat that card.
- Next, turn b face up.
- If 2 is written on b, eat that card.
  - Next, turn c face up; since 3 is necessarily written on it, eat it. In this case, you eat all cards in three operations, and the probability of this happening is 1/6.
- If 3 is written on b, turn that card face down.
  - Next, turn c face up; since 2 is necessarily written on it, eat it. After that, turn b face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is 1/6.
If 2 is written on a, turn that card face down.
- Next, turn b face up.
- If 1 is written on b, eat that card.
  - Next, turn a face up and eat it. Next, turn c face up; since 3 is necessarily written on it, eat it. In this case, you eat all cards in four operations, and the probability of this happening is 1/6.
- If 3 is written on b, turn that card face down.
  - At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is 1/6.
If 3 is written on a, turn that card face down.
- Next, turn b face up.
- If 1 is written on b, eat that card.
  - Next, turn c face up; since 2 is necessarily written on it, eat it. After that, turn a face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is 1/6.
- If 2 is written on b, turn that card face down.
  - At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is 1/6.

Combining everything, the probability that the total number of operations is 3 is 1/6, the probability that it is 4 is 1/2, and the probability that it is 5 is 1/3.
For this sample, output 499122177, which represents 1/2 modulo 998244353.

Sample Input 2

3 6

Sample Output 2

Sample Input 3

500000 777777

Sample Output 3

251612105