Problem 814

Mezzo-forte

$4 n$ people stand in a circle with their heads down. When the bell rings they all raise their heads and either look at the person immediately to their left, the person immediately to their right or the person diametrically opposite. If two people find themselves looking at each other they both scream.

Define $S (n)$ to be the number of ways that exactly half of the people scream. You are given $S (1) = 48$ and $S (10) \equiv 420121075 (\mod 998244353)$ .

Find $S (10^{3})$ . Enter your answer modulo $998244353$ .

中强音

$4 n$ 个人低头站成一圈，当钟声响起时，每个人都抬起头，或者看向紧靠其左侧的人，或者看向紧靠其右侧的人，或者看向其正对面的人。如果两个人恰好对视，则会同时尖叫。

记 $S (n)$ 为恰好有一半人尖叫的对视方案数量。已知 $S (1) = 48$ ， $S (10) \equiv 420121075 (\mod 998244353)$ 。

求 $S (10^{3})$ ，并将你的答案对 $998244353$ 取余。

译注：Mezzo-forte是意大利语音乐术语，表示“中等偏强”。