acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem D

IPvK

4 人の候補者から 1 人を選出する選挙の投票結果を見てある人がこう言った.「この数字は IPv4 アドレスに見えるね」

あなたはこれを,任意の K つ組について一般化することにした.すなわち,任意の正整数 K について,IPvK アドレスを「0 以上 255 以下の整数の K つ組を . で連結したもの」と定義する.

いま,N 人の有権者と K 人の候補者からなる選挙が行われようとしている.各候補者には 1 から K までの番号が付けられている.各有権者は K 人の候補者の中のいずれかひとりに投票する.ただし,棄権や無効票,按分票はないものとする.したがって,各候補者の得票数は 0 以上の整数であり,かつ,全候補者の得票数の総和は N 票である.なお,無記名投票のため,どの有権者がどの候補者に投票したかは区別しないものとする.

ここで, K 人の候補者の得票数を 1 番の候補者のものから順に . で連結したものであって, IPvK アドレスとみなせるようなものからなる集合を考える.それぞれについて K 人の候補者の得票数の積を求め,それらすべての総和を 998,244,353 で割った余りを求めよ.

Input

入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.

K N

整数 K および N が与えられる.K は候補者の人数であり,1 ≤ K ≤ 2,000 を満たす.N は有権者の人数であり,1 ≤ N ≤ K × 255 を満たす.

入力の終わりは 2 つのゼロからなる行で表される.

Output

各データセットに対し,答えを一行に出力せよ.

Sample Input

4 3
2 510
4 5
271 828
2000 133333
0 0

Sample Output

0
65025
8
53634343
781942874

最初のデータセットでは,4 人の候補者の得票数の積は常に 0 となるため,その総和も 0 となる.

二番目のデータセットでは,2 人の候補者が 255 票ずつ得たとき,またそのときに限り,得票数を連結したものを IPv2 アドレスとみなせる.したがって,255 × 255 = 65025 が答えとなる.

(End of Problem D) A B C D E F G H