Շախմատի փիղ

Շախմատում կան մի քանի տեսակի խաղաքարեր, որոնցից յուրաքանչյուրը իրա շարժման կանոններն ունի։ Մասնավորապես, փիղը կարող է շարժվել անկյունագծերով՝ 4 ուղղություններով։ Կարելի է պատկերացնել, որ բազմաչափ տախտակում փիղը նույնպես կշարժվի անկյունագծերով։ d չափանի $n × n$տախտակի վրա $x_1, x_2, ..., x_d$կետից կարող է հասնել $x_1 + c · s_1, x_2 + c · s_2, ..., x_d + c · s_d$տախտակի վրա գտնվող ցանկացած վանդակ, որտեղ c֊ն բնական թիվ է, իսկ $s_i$֊երը 1 կամ -1 են։ Հաշվեք քանի վանդակ կարող է գնալ նշված դիրքում գտնվող շախմատի փիղը։

Մուտքային տվյալներ

Առաջին տողում տրված է բնական թիվ d և n թվերը՝ տարածության առանցնքերի քանակն ու տախտակի չափը։ Հաջորդ տողում տրված են բացատով անջատված d բնական թվեր՝ $x_1, x_2, ..., x_d (1 ≤ x_i ≤ n)$։

Ելքային տվյալներ

Պետք է արտածել 1 թիվ՝ հնարավոր քայլերի քանակը։ Քանի որ այն կարող է շատ մեծ լինել, արտածեք նրա 998244353֊ի վրա բաժանելիս ստացվող մնացորդը։

Օրինակ

Բացատրություն

Առաջին թեստի բացատրության համար տես ստորև նկարը։

Երկրորդ թեստում բոլոր հասանելի վանդակներն են (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8) ֊ը։

Ենթախնդիրներ

• Ենթախնդիր 0 (0 միավոր) Օրինակները,

• Ենթախնդիր 1 (5 միավոր) $d = 2, 1 ≤ n ≤ 10^8$

• Ենթախնդիր 2 (5 միավոր) $d = 3, 1 ≤ n ≤ 10^8$

• Ենթախնդիր 3 (12 միավոր) $1 ≤ d ≤ 10, 1 ≤ n ≤ 5$

• Ենթախնդիր 4 (28 միավոր) $1 ≤ d ≤ 20, 1 ≤ n ≤ 10^8$

• Ենթախնդիր 5 (5 միավոր) $1 ≤ d ≤ 300000, 1 ≤ n ≤ 10^8, x_1 = x_2 = ... = x_d$

• Ենթախնդիր 6 (45 միավոր) $1 ≤ d ≤ 300000, 1 ≤ n ≤ 10^8$