There are n heroes fighting in the arena. Initially, the i-th hero has a_i health points.

The fight in the arena takes place in several rounds. At the beginning of each round, each alive hero deals 1 damage to all other heroes. Hits of all heroes occur simultaneously. Heroes whose health is less than 1 at the end of the round are considered killed.

If exactly 1 hero remains alive after a certain round, then he is declared the winner. Otherwise, there is no winner.

Your task is to calculate the number of ways to choose the initial health points for each hero a_i, where 1 ≤ a_i ≤ x, so that there is no winner of the fight. The number of ways can be very large, so print it modulo 998244353. Two ways are considered different if at least one hero has a different amount of health. For example, [1, 2, 1] and [2, 1, 1] are different.

Input

The only line contains two integers n and x (2 ≤ n ≤ 500; 1 ≤ x ≤ 500).

Output

Print one integer — the number of ways to choose the initial health points for each hero a_i, where 1 ≤ a_i ≤ x, so that there is no winner of the fight, taken modulo 998244353. 

Examples

Input


2 5


Output


5


Input


3 3


Output


15


Input


5 4


Output


1024


Input


13 37


Output


976890680

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
import functools
MOD_NUM = 998244353
COMB = [[0] * 510 for _ in range(510)]
for n in range(510):
	for k in range(1 + n):
		if n == k or k == 0:
			COMB[n][k] = 1
			continue
		COMB[n][k] = COMB[n - 1][k] + COMB[n - 1][k - 1]
		COMB[n][k] %= MOD_NUM

def comb(n, k):
	return COMB[n][k]

@functools.lru_cache(None)
def dp(n, x):
	if x <= n - 1:
		if n > 1:
			return pow(x, n, MOD_NUM)
		else:
			return 0
	ans = pow(n - 1, n, MOD_NUM)
	for k in range(2, n + 1):
		ans += comb(n, k) * pow(n - 1, n - k, MOD_NUM) * dp(k, x - n + 1)
		ans %= MOD_NUM
	return ans
(n, x) = map(int, input().split())
print(dp(n, x))


N = 5000
mod = 998244353
fac = [1] * (N + 1)
finv = [1] * (N + 1)
for i in range(N):
	fac[i + 1] = fac[i] * (i + 1) % mod
finv[-1] = pow(fac[-1], mod - 2, mod)
for i in reversed(range(N)):
	finv[i] = finv[i + 1] * (i + 1) % mod

def cmb1(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return fac[n] * finv[r] * finv[n - r] % mod
(n, x) = map(int, input().split())
dp = [[0] * (x + 1) for i in range(n + 1)]
dp[n][0] = 1
for i in reversed(range(1, n + 1)):
	for j in range(x + 1):
		if not dp[i][j]:
			continue
		nj = min(x, i + j - 1)
		for k in reversed(range(i + 1)):
			dp[k][nj] += cmb1(i, i - k, mod) * pow(nj - j, i - k, mod) * dp[i][j]
			dp[k][nj] %= mod
ans = 0
for i in range(x + 1):
	ans += dp[0][i]
	ans %= mod
print(ans)


(n, x) = map(int, input().split(' '))
modulus = 998244353
negceil = lambda x: 0 if x < 0 else x
dp = [[-1 for _ in range(2000)] for _ in range(505)]
mx = 505
fac = [1] * mx
for i in range(1, mx):
	fac[i] = fac[i - 1] * i % modulus
ifac = [1] * 505
ifac[-1] = pow(fac[-1], modulus - 2, modulus)
for i in range(mx - 2, 0, -1):
	ifac[i] = (i + 1) * ifac[i + 1] % modulus

def C(a, b):
	return fac[a] * ifac[a - b] % modulus * ifac[b] % modulus

def solve(rem, thresh):
	prev_thresh = thresh - rem + 1
	global dp
	if rem == 1:
		return 0
	if rem == 0:
		return 1
	if prev_thresh >= x:
		return 0
	if dp[rem][thresh] != -1:
		return dp[rem][thresh]
	dp[rem][thresh] = 0
	for p in range(rem + 1):
		combs = C(rem, p)
		assigns = pow(min(thresh, x) - prev_thresh, p, modulus)
		dp[rem][thresh] += combs * assigns * solve(rem - p, thresh + (rem - p - 1))
		dp[rem][thresh] %= modulus
	return dp[rem][thresh]
print(solve(n, n - 1))


m = 998244353
(n, x) = map(int, input().split())
if n >= x + 1:
	prod = 1
	for i in range(n):
		prod = prod * x % m
	print(prod)
else:
	binomial = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(i + 1):
			binomial[i][j] = 1 if i == j or j == 0 else (binomial[i - 1][j] + binomial[i - 1][j - 1]) % m
	table = [[0] * (n + 1) for i in range(x + 1)]
	powers = [[0] * (n + 1) for i in range(n + 1)]
	combo = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(n + 1):
		powers[i][0] = 1
		for j in range(n):
			powers[i][j + 1] = powers[i][j] * i % m
	for j in range(1, n + 1):
		for k in range(j + 1):
			combo[j][k] = powers[j - 1][j - k] * binomial[j][k] % m
	for i in range(2, n + 1):
		table[1][i] = 1
	for i in range(1, x + 1):
		table[i][0] = 1
	for i in range(2, x + 2 - n):
		for j in range(2, n + 1):
			if j == i + 1:
				prod = 1
				for k in range(j):
					prod = prod * i % m
				table[i][j] = prod
			elif j > i:
				table[i][j] = table[i][j - 1] * i % m
			else:
				table[i][j] = sum((table[i - j + 1][k] * combo[j][k] for k in range(j + 1))) % m
	print(sum((table[x - n + 1][k] * combo[n][k] for k in range(n + 1))) % m)


from functools import lru_cache
(n, x) = map(int, input().split(' '))
modulus = 998244353
mx = 505
fac = [1] * mx
for i in range(1, mx):
	fac[i] = fac[i - 1] * i % modulus
ifac = [1] * 505
ifac[-1] = pow(fac[-1], modulus - 2, modulus)
for i in range(mx - 2, 0, -1):
	ifac[i] = (i + 1) * ifac[i + 1] % modulus

def C(a, b):
	return fac[a] * ifac[a - b] % modulus * ifac[b] % modulus

@lru_cache(None)
def solve(rem, thresh):
	prev_thresh = thresh - rem + 1
	global dp
	if rem == 1:
		return 0
	if rem == 0:
		return 1
	if prev_thresh >= x:
		return 0
	s = 0
	for p in range(rem + 1):
		combs = C(rem, p)
		assigns = pow(min(thresh, x) - prev_thresh, p, modulus)
		s += combs * assigns * solve(rem - p, thresh + (rem - p - 1))
		s %= modulus
	return s
print(solve(n, n - 1))


import sys
input = lambda : sys.stdin.readline().strip()
from functools import lru_cache
mod = 998244353
mx = 505
fac = [1] * mx
for i in range(1, mx):
	fac[i] = fac[i - 1] * i % mod
ifac = [1] * 505
ifac[-1] = pow(fac[-1], mod - 2, mod)
for i in range(mx - 2, 0, -1):
	ifac[i] = (i + 1) * ifac[i + 1] % mod

def comb(a, b):
	return fac[a] * ifac[a - b] % mod * ifac[b] % mod

@lru_cache(None)
def helper(n, x):
	if x <= n - 1:
		return pow(x, n, mod)
	res = pow(n - 1, n, mod)
	for j in range(2, n + 1):
		res += comb(n, j) * helper(j, x - n + 1) * pow(n - 1, n - j, mod)
		res %= mod
	return res

def solve():
	(n, x) = map(int, input().split())
	return helper(n, x)
print(solve())


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
from functools import lru_cache
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inps():
	return input().strip()

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
mod = 998244353
p = mod
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def recur(vn, vx):
	if vn == 1:
		dp[vn][vx] = vx
		yield vx
	if vx <= vn - 1:
		dp[vn][vx] = 0
		yield 0
	if dp[vn][vx] != -1:
		yield dp[vn][vx]
	res = 0
	for u in range(1, vn + 1):
		res += (yield recur(u, vx - vn + 1)) * powerMod(vn - 1, vn - u, mod) * comb[vn][u]
		res %= p
	dp[vn][vx] = res
	yield res

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
(n, x) = invr()
dp = [[-1 for i in range(x + 1)] for j in range(n + 1)]
if n > x:
	print(powerMod(x, n, mod))
else:
	comb = [[0 for j in range(n + 1)] for i in range(n + 1)]
	comb[0][0] = 1
	for i in range(1, n + 1):
		comb[i][0] = 1
		comb[i][i] = 1
		for j in range(1, i):
			comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % p
	recur(n, x)
	ans = (powerMod(x, n, p) - dp[n][x]) % mod
	print(ans)