Background

Special for beginners, ^_^

Description

注：答案对 998244353 取模.

Format

Input

Output

Samples

5

90

1000

501000500

Limitation

对于20%的数据，n<=100。 对于40%的数据，n<=2000。 对于100%的数据，n<=10的18次方。