Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

combinatorics

dp

fft

math

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Function Sum

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSuppose you have an integer array $$$a_1, a_2, \dots, a_n$$$.

Let $$$\operatorname{lsl}(i)$$$ be the number of indices $$$j$$$ ($$$1 \le j < i$$$) such that $$$a_j < a_i$$$.

Analogically, let $$$\operatorname{grr}(i)$$$ be the number of indices $$$j$$$ ($$$i < j \le n$$$) such that $$$a_j > a_i$$$.

Let's name position $$$i$$$ good in the array $$$a$$$ if $$$\operatorname{lsl}(i) < \operatorname{grr}(i)$$$.

Finally, let's define a function $$$f$$$ on array $$$a$$$ $$$f(a)$$$ as the sum of all $$$a_i$$$ such that $$$i$$$ is good in $$$a$$$.

Given two integers $$$n$$$ and $$$k$$$, find the sum of $$$f(a)$$$ over all arrays $$$a$$$ of size $$$n$$$ such that $$$1 \leq a_i \leq k$$$ for all $$$1 \leq i \leq n$$$ modulo $$$998\,244\,353$$$.

Input

The first and only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 50$$$; $$$2 \leq k < 998\,244\,353$$$).

Output

Output a single integer — the sum of $$$f$$$ over all arrays $$$a$$$ of size $$$n$$$ modulo $$$998\,244\,353$$$.

Examples

Input

3 3

Output

28

Input

5 6

Output

34475

Input

12 30

Output

920711694

Note

In the first test case:

$$$f([1,1,1]) = 0$$$ | $$$f([2,2,3]) = 2 + 2 = 4$$$ |

$$$f([1,1,2]) = 1 + 1 = 2$$$ | $$$f([2,3,1]) = 2$$$ |

$$$f([1,1,3]) = 1 + 1 = 2$$$ | $$$f([2,3,2]) = 2$$$ |

$$$f([1,2,1]) = 1$$$ | $$$f([2,3,3]) = 2$$$ |

$$$f([1,2,2]) = 1$$$ | $$$f([3,1,1]) = 0$$$ |

$$$f([1,2,3]) = 1$$$ | $$$f([3,1,2]) = 1$$$ |

$$$f([1,3,1]) = 1$$$ | $$$f([3,1,3]) = 1$$$ |

$$$f([1,3,2]) = 1$$$ | $$$f([3,2,1]) = 0$$$ |

$$$f([1,3,3]) = 1$$$ | $$$f([3,2,2]) = 0$$$ |

$$$f([2,1,1]) = 0$$$ | $$$f([3,2,3]) = 2$$$ |

$$$f([2,1,2]) = 1$$$ | $$$f([3,3,1]) = 0$$$ |

$$$f([2,1,3]) = 2 + 1 = 3$$$ | $$$f([3,3,2]) = 0$$$ |

$$$f([2,2,1]) = 0$$$ | $$$f([3,3,3]) = 0$$$ |

$$$f([2,2,2]) = 0$$$ |

Adding up all of these values, we get $$$28$$$ as the answer.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 11:46:58 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|