A - N-choice question

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100

問題文

整数 A,B が与えられるので、 A+B の値を答えてください。
但し、この問題は N 択問題であり、 i 番の選択肢は C_i です。
正解となる 選択肢の番号 を出力してください。

制約

  • 入力は全て整数
  • 1 \le N \le 300
  • 1 \le A,B \le 1000
  • 1 \le C_i \le 2000
  • C_i は相異なる。すなわち、同じ選択肢が複数存在することはない。
  • A+B=C_i なる i が丁度 1 つ存在する。すなわち、正解となる選択肢が必ずただ 1 つ存在する。

入力

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

N A B
C_1 C_2 \dots C_N

出力

答えを整数として出力せよ。


入力例 1

3 125 175
200 300 400

出力例 1

2

125+175 = 300 です。
1 番の選択肢は 2002 番の選択肢は 3003 番の選択肢は 400 です。
よって正解となる選択肢の番号は 2 番であり、これを出力します。


入力例 2

1 1 1
2

出力例 2

1

1 択問題である場合もあります。


入力例 3

5 123 456
135 246 357 468 579

出力例 3

5

Score : 100 points

Problem Statement

Given integers A and B, find A+B.
This is a N-choice problem; the i-th choice is C_i.
Print the index of the correct choice.

Constraints

  • All values in the input are integers.
  • 1 \le N \le 300
  • 1 \le A,B \le 1000
  • 1 \le C_i \le 2000
  • C_i are pairwise distinct. In other words, no two choices have the same value.
  • There is exactly one i such that A+B=C_i. In other words, there is always a unique correct choice.

Input

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

N A B
C_1 C_2 \dots C_N

Output

Print the answer as an integer.


Sample Input 1

3 125 175
200 300 400

Sample Output 1

2

We have 125+175 = 300.
The first, second, and third choices are 200, 300, and 400, respectively.
Thus, the 2-nd choice is correct, so 2 should be printed.


Sample Input 2

1 1 1
2

Sample Output 2

1

The problem may be a one-choice problem.


Sample Input 3

5 123 456
135 246 357 468 579

Sample Output 3

5
B - Same Map in the RPG World

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200

問題文

高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。

H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには #. のいずれかの文字が書かれています。
AB の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。

次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。

  • j=1, 2, \dots, W について次の操作を同時に行う。
    • A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j}A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j} に同時に置き換える。
  • i = 1, 2, \dots, H について次の操作を同時に行う。
    • A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W}A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1} に同時に置き換える。

次の条件を満たす非負整数の組 (s, t) は存在しますか?存在する場合は Yes を、存在しない場合は No を出力してください。

  • 縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の AB と一致する。

ここで、AB が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して A_{i, j} = B_{i, j} が成り立つことを言います。

制約

  • 2 \leq H, W \leq 30
  • A_{i,j},B_{i,j}# または .
  • H, W は整数

入力

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

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

出力

条件を満たす整数の組 (s, t) が存在する場合は Yes を、存在しない場合は No を出力せよ。


入力例 1

4 3
..#
...
.#.
...
#..
...
.#.
...

出力例 1

Yes

(s, t) = (2, 1) とすると AB を一致させることができます。
(s, t) = (2, 1) の時の操作の手順を説明します。はじめ、A は次の通りです。

..#
...
.#.
...

まず、縦方向のシフトを行います。A は次のようになります。

...
.#.
...
..#

次に、再び縦方向のシフトを行います。A は次のようになります。

.#.
...
..#
...

最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。

#..
...
.#.
...

入力例 2

3 2
##
##
#.
..
#.
#.

出力例 2

No

どのように (s, t) を選んでも AB を一致させることはできません。


入力例 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

出力例 3

Yes

入力例 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

出力例 4

Yes

Score : 200 points

Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

  • For each j=1, 2, \dots, W, simultaneously do the following:
    • simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
  • For each i = 1, 2, \dots, H, simultaneously do the following:
    • simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

  • After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

  • 2 \leq H, W \leq 30
  • A_{i,j} is # or ., and so is B_{i,j}.
  • H and W are integers.

Input

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

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

Output

Print Yes if there is a conforming integer pair (s, t); print No otherwise.


Sample Input 1

4 3
..#
...
.#.
...
#..
...
.#.
...

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

..#
...
.#.
...

We first apply a vertical shift to make A as follows.

...
.#.
...
..#

Then we apply another vertical shift to make A as follows.

.#.
...
..#
...

Finally, we apply a horizontal shift to make A as follows, which equals B.

#..
...
.#.
...

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.


Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes
C - Cross

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300

問題文

H マス横 W マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスには #. のいずれかの文字が書かれています。(i, j) に書かれている文字を C[i][j] とします。また、整数 i, j1 \leq i \leq H1 \leq j \leq W の少なくとも一方を満たさない場合、 C[i][j]. と定義します。

正整数 a, b, n が以下の条件を全て満たす時、(a,b) および (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n)4n + 1 マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。

  • C[a][b]# である。
  • 1 \leq d \leq n を満たす整数 d について、 C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d] はいずれも # である。
  • C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1] のうち少なくとも 1 つは . である。

例えば次の図で示された例では、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印がグリッド上にあります。

image

グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。
また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは (3, 3)(4, 4) が頂点を共有しているのが条件に反しています。

image2

N = \min(H, W) とします。また、サイズ n のバツ印の個数を S_n とします。S_1, S_2, \dots, S_N を計算してください。

制約

  • 3 \leq H, W \leq 100
  • C[i][j]# または .
  • 異なるバツ印を構成するマス同士は頂点を共有しない
  • H, W は整数

入力

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

出力

S_1, S_2, \dots, S_N を空白区切りで出力せよ。


入力例 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

出力例 1

1 1 0 0 0

問題文に書かれた説明の通り、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印が書かれています。


入力例 2

3 3
...
...
...

出力例 2

0 0 0

バツ印が 1 個も書かれていない場合もあります。


入力例 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

出力例 3

3 0 0

入力例 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

出力例 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

  • C[a][b] is #.
  • C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
  • At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

image

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

image2

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

  • 3 \leq H, W \leq 100
  • C[i][j] is # or ..
  • No two different squares that comprise two different crosses share a corner.
  • H and W are integers.

Input

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

Output

Print S_1, S_2, \dots, and S_N, separated by spaces.


Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).


Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.


Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0
D - AABCC

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 400

問題文

N 以下の正整数のうち、 a<b<c なる 素数 a,b,c を用いて a^2 \times b \times c^2 と表せるものはいくつありますか?

制約

  • N300 \le N \le 10^{12} を満たす整数

入力

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

N

出力

答えを整数として出力せよ。


入力例 1

1000

出力例 1

3

1000 以下で条件を満たす整数は以下の 3 つです。

  • 300 = 2^2 \times 3 \times 5^2
  • 588 = 2^2 \times 3 \times 7^2
  • 980 = 2^2 \times 5 \times 7^2

入力例 2

1000000000000

出力例 2

2817785

Score : 400 points

Problem Statement

How many positive integers no greater than N can be represented as a^2 \times b \times c^2 with three primes a,b, and c such that a<b<c?

Constraints

  • N is an integer satisfying 300 \le N \le 10^{12}.

Input

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

N

Output

Print the answer as an integer.


Sample Input 1

1000

Sample Output 1

3

The conforming integers no greater than 1000 are the following three.

  • 300 = 2^2 \times 3 \times 5^2
  • 588 = 2^2 \times 3 \times 7^2
  • 980 = 2^2 \times 5 \times 7^2

Sample Input 2

1000000000000

Sample Output 2

2817785
E - Dice Product 3

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500

問題文

あなたは 1 以上 6 以下の整数が等確率で出るサイコロと整数 1 を持っています。
あなたは持っている整数が N 未満である間、次の操作を繰り返します。

  • サイコロを振り、出た目を x とする。持っている整数に x を掛ける。

全ての操作を終了した時に、持っている整数が N に一致する確率を \text{mod }998244353 で求めてください。

確率 \text{mod }998244353 とは? 求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

  • 2 \leq N \leq 10^{18}
  • N は整数

入力

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

N

出力

全ての操作を終了した時に、持っている整数が N に一致する確率を \text{mod }998244353 で出力せよ。


入力例 1

6

出力例 1

239578645

操作が終了するまでの手順としてあり得る一例を挙げると次のようになります。

  • はじめ, 持っている整数は 1 である。
  • サイコロを振り, 2 が出る。持っている整数は 1 \times 2 = 2 になる。
  • サイコロを振り, 4 が出る。持っている整数は 2 \times 4 = 8 になる。
  • 持っている整数が 6 以上になったので操作を終了する。

操作がこのように進んだ場合、操作後に持っている整数は 8 であり N = 6 に一致しません。

操作後に持っている整数が 6 である確率は \frac{7}{25} です。 239578645 \times 25 \equiv 7 \pmod{998244353} より、 239578645 を出力してください。


入力例 2

7

出力例 2

0

どのような目が出ても、操作後に持っている整数が 7 になることはありません。


入力例 3

300

出力例 3

183676961

入力例 4

979552051200000000

出力例 4

812376310

Score : 500 points

Problem Statement

You have an integer 1 and a die that shows integers between 1 and 6 (inclusive) with equal probability.
You repeat the following operation while your integer is strictly less than N:

  • Cast a die. If it shows x, multiply your integer by x.

Find the probability, modulo 998244353, that your integer ends up being N.

How to find a probability modulo 998244353? We can prove that the sought probability is always rational. Additionally, under the constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

  • 2 \leq N \leq 10^{18}
  • N is an integer.

Input

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

N

Output

Print the probability, modulo 998244353, that your integer ends up being N.


Sample Input 1

6

Sample Output 1

239578645

One of the possible procedures is as follows.

  • Initially, your integer is 1.
  • You cast a die, and it shows 2. Your integer becomes 1 \times 2 = 2.
  • You cast a die, and it shows 4. Your integer becomes 2 \times 4 = 8.
  • Now your integer is not less than 6, so you terminate the procedure.

Your integer ends up being 8, which is not equal to N = 6.

The probability that your integer ends up being 6 is \frac{7}{25}. Since 239578645 \times 25 \equiv 7 \pmod{998244353}, print 239578645.


Sample Input 2

7

Sample Output 2

0

No matter what the die shows, your integer never ends up being 7.


Sample Input 3

300

Sample Output 3

183676961

Sample Input 4

979552051200000000

Sample Output 4

812376310
F - More Holidays

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500

問題文

ox からなる長さ N の文字列 S と、整数 M,K が与えられます。
S には少なくとも 1 つの x が含まれることが保証されます。

SM 個連結して得られる長さ NM の文字列を T とします。 T に含まれる x のうち丁度 K 個を選んで o に変えることを考えます。
あなたの目標は、変更後の To のみからなるできるだけ長い連続部分文字列が含まれるようにすることです。
o のみからなる連続部分文字列の長さとして達成可能な最大値を求めてください。

制約

  • N,M,K は整数
  • 1 \le N \le 3 \times 10^5
  • 1 \le M \le 10^9
  • x を文字列 T に含まれる x の総数としたとき、 1 \le K \le x
  • Sox からなる長さ N の文字列
  • S には少なくとも 1 つの x が含まれる

入力

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

N M K
S

出力

答えを整数として出力せよ。


入力例 1

10 1 2
ooxxooooox

出力例 1

9

S= ooxxoooooxT= ooxxooooox です。
3 文字目と 4 文字目の xo に変更することにより、変更後の T= ooooooooox となります。
このとき o のみからなる長さ 9 の連続部分文字列が得られ、これが達成可能な最大値です。


入力例 2

5 3 4
oxxox

出力例 2

8

S= oxxoxT= oxxoxoxxoxoxxox です。
5,7,8,10 文字目の xo に変更することにより、変更後の T= oxxooooooooxxox となります。
このとき o のみからなる長さ 8 の連続部分文字列が得られ、これが達成可能な最大値です。


入力例 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

出力例 3

19964887064

Score : 500 points

Problem Statement

You are given a string S of length N consisting of o and x, and integers M and K.
S is guaranteed to contain at least one x.

Let T be the string of length NM obtained by concatenating M copies of S. Consider replacing exactly K x's in T with o.
Your objective is to have as long a contiguous substring consisting of o as possible in the resulting T.
Find the maximum length of a contiguous substring consisting of o that you can obtain.

Constraints

  • N, M, and K are integers.
  • 1 \le N \le 3 \times 10^5
  • 1 \le M \le 10^9
  • 1 \le K \le x, where x is the number of x's in the string T.
  • S is a string of length N consisting of o and x.
  • S has at least one x.

Input

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

N M K
S

Output

Print the answer as an integer.


Sample Input 1

10 1 2
ooxxooooox

Sample Output 1

9

S= ooxxooooox and T= ooxxooooox.
Replacing x at the third and fourth characters with o makes T= ooooooooox.
Now we have a length-9 contiguous substring consisting of o, which is the longest possible.


Sample Input 2

5 3 4
oxxox

Sample Output 2

8

S= oxxox and T= oxxoxoxxoxoxxox.
Replacing x at the 5,7,8 and 10-th characters with o makes T= oxxooooooooxxox.
Now we have a length-8 contiguous substring consisting of o, which is the longest possible.


Sample Input 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

Sample Output 3

19964887064
G - P-smooth number

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 600

問題文

k 以下の素数のみを素因数に持つ正整数を k-smooth number と呼びます。
整数 N および 100 以下の素数 P が与えられるので、 N 以下の P-smooth number の個数を求めてください。

制約

  • N1 \le N \le 10^{16} を満たす整数
  • P2 \le P \le 100 を満たす素数

入力

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

N P

出力

答えを整数として出力せよ。


入力例 1

36 3

出力例 1

14

36 以下の 3-smooth number は 1,2,3,4,6,8,9,12,16,18,24,27,32,3614 個です。
1 は任意の素数 k に対して k-smooth number であることに注意してください。


入力例 2

10000000000000000 97

出力例 2

2345134674

Score : 600 points

Problem Statement

A positive integer is called a k-smooth number if none of its prime factors exceeds k.
Given an integer N and a prime P not exceeding 100, find the number of P-smooth numbers not exceeding N.

Constraints

  • N is an integer such that 1 \le N \le 10^{16}.
  • P is a prime such that 2 \le P \le 100.

Input

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

N P

Output

Print the answer as an integer.


Sample Input 1

36 3

Sample Output 1

14

The 3-smooth numbers not exceeding 36 are the following 14 integers: 1,2,3,4,6,8,9,12,16,18,24,27,32,36.
Note that 1 is a k-smooth number for all primes k.


Sample Input 2

10000000000000000 97

Sample Output 2

2345134674
Ex - Fibonacci: Revisited

実行時間制限: 6 sec / メモリ制限: 1024 MB

配点 : 600

問題文

数列 a_0, a_1, a_2, \dots の一般項 a_n を次のように定義します。

a_n = \begin{cases} 1 & (0 \leq n \lt K) \\ \displaystyle{\sum_{i=1}^K} a_{n-i} & (K \leq n) \\ \end{cases}


整数 N が与えられます。m\text{ AND }N = m を満たす全ての非負整数 m に対する a_m の総和を 998244353 で割った余りを求めてください。(\text{AND} はビット単位 AND)

ビット単位 AND とは? 整数 A,B のビット単位 AND、A\text{ AND }B は以下のように定義されます。
A\text{ AND }B を二進表記した際の 2^k (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。

制約

  • 1 \leq K \leq 5 \times 10^4
  • 0 \leq N \leq 10^{18}
  • N, K は整数

入力

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

K N

出力

答えを出力せよ。


入力例 1

2 6

出力例 1

21

数列の各項を a_0 から順に並べると 1, 1, 2, 3, 5, 8, 13, 21, \dots になります。
6 \text{ AND } m = m であるような非負整数は 0, 2, 4, 6 の 4 個なので、答えは 1 + 2 + 5 + 13 = 21 になります。


入力例 2

2 8

出力例 2

35

入力例 3

1 123456789

出力例 3

65536

入力例 4

300 20230429

出力例 4

125461938

入力例 5

42923 999999999558876113

出力例 5

300300300

Score : 600 points

Problem Statement

We define the general term a_n of a sequence a_0, a_1, a_2, \dots by:

a_n = \begin{cases} 1 & (0 \leq n \lt K) \\ \displaystyle{\sum_{i=1}^K} a_{n-i} & (K \leq n). \\ \end{cases}


Given an integer N, find the sum, modulo 998244353, of a_m over all non-negative integers m such that m\text{ AND }N = m. (\text{AND} denotes the bitwise AND.)

What is bitwise AND? The bitwise AND of non-negative integers A and B, A\text{ AND }B, is defined as follows.
・When A\text{ AND }B is written in binary, its 2^ks place (k \geq 0) is 1 if 2^ks places of A and B are both 1, and 0 otherwise.

Constraints

  • 1 \leq K \leq 5 \times 10^4
  • 0 \leq N \leq 10^{18}
  • N and K are integers.

Input

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

K N

Output

Print the answer.


Sample Input 1

2 6

Sample Output 1

21

a_0 and succeeding terms are 1, 1, 2, 3, 5, 8, 13, 21, \dots. Four non-negative integers, 0, 2, 4, and 6, satisfy 6 \text{ AND } m = m, so the answer is 1 + 2 + 5 + 13 = 21.


Sample Input 2

2 8

Sample Output 2

35

Sample Input 3

1 123456789

Sample Output 3

65536

Sample Input 4

300 20230429

Sample Output 4

125461938

Sample Input 5

42923 999999999558876113

Sample Output 5

300300300