Avoiding Forbidden Student Grouping

The academy of Da Zhongfeng is organizing a museum visit where students must line up in a queue. There are four types of students, each with a distinct favorite activity: Singing, Dancing, Rap, and Basketball. If there exists any four consecutive positions \(k, k+1, k+2, k+3\) in the queue whose preferences are, in order, Singing, Dancing, Rap, and Basketball (i.e. if \(a_k=\mathtt{0}\), \(a_{k+1}=\mathtt{1}\), \(a_{k+2}=\mathtt{2}\) and \(a_{k+3}=\mathtt{3}\), where we represent Singing by 0, Dancing by 1, Rap by 2 and Basketball by 3), then those students will gather to discuss Cai Xukun, which disrupts the order of the line.

Da Zhongfeng wants to know in how many ways the students can be arranged in a queue so that no such forbidden pattern occurs. Two arrangements are considered different if at least one position in the queue has a student with a different preference. Since the number of valid arrangements can be very large, output the answer modulo \(998244353\).

Input Format: A single integer \(n\) denoting the number of students in the queue.

Output Format: Output one integer -- the number of valid arrangements modulo \(998244353\).

inputFormat

The input consists of a single line which contains a positive integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of students in the queue.

outputFormat

Output a single integer: the number of valid arrangements modulo \(998244353\).

sample

1

4