Дано ціле число \(N\). Знайдіть кількість цілих чисел \(X\), які задовольняють усі наступні умови, за модулем 998244353.

\(X\) — \(N\)-значне натуральне число.

Нехай \(X_1,X_2,\dots,X_N\) цифри \(X\) зверху вниз. Вони задовольняють усі наступні параметри:

• \(1 \le X_i \le 9\) для всіх цілих чисел \(1 \le i \le N\);

• \(|X_i-X_{i+1}| \le 1\) для всіх цілих чисел \(1 \le i \le N-1\).

Формат вхідних даних

Вхідний потік містить ціле число \(N\) (\(2 \le N \le 10^6\))

Формат вихідних даних

У вихідний потік виведіть шукану кількість.

Примітка

До прикладу 1:

Деякі з 4-значних цілих чисел, що задовольняють умовам, є 1111,1234,7878,6545.

Приклад вхідних даних

4

Приклад вихідних даних

203

Приклад вхідних даних

2

Приклад вихідних даних

25

Приклад вхідних даних

1000000

Приклад вихідних даних

248860093