410415: GYM104018 H Громогласность

H. Громогласностьограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Как известно, в кыргызском языке есть 8 кратких гласных букв: а, э(е), ы, и, о, ө, у, ү.

Айбек считает родной язык очень важной частью культуры, поэтому стремится сделать какой-то ощутимый и полезный вклад — расширить возможности языка.

Недавно Айбек изобрёл новый вид слов — «гласнометия». Гласнометием является слово, состоящее только из гласных букв.

Оказалось, что некоторые гласнометия произносить очень легко, а некоторые — невероятно трудно. Айбек предполагает, что всему виной отверстия в буквах:

• в буквах и, у, ү отверстий нет вообще;
• в буквах а, ы, о есть ровно одно отверстие;
• в букве ө целых два отверстия;
• у буквы э(е) одно отверстие на два различных написания — по логике Айбека это ровно половина отверстия на одно написание.

Айбек выдвинул гипотезу, что проще всего произносить гласнометия, которые сбалансированы — количества «отверстий» на четных и нечетных позициях совпадают.

Теперь Айбек просит вас, как знатока $$$100500$$$ диалектов компьютерного кыргызского сленга, вычислить количество сбалансированных гласнометий, состоящих ровно из $$$N$$$ букв.

Так как количество может быть слишком велико для осознания простого смертного, Айбек хочет узнать лишь остаток от деления искомого количества на $$$2022$$$.

Входные данные

В единственной строке задано целое число $$$N$$$ $$$(1 \le N \le 2022)$$$ — количество букв в интересующих Айбека гласнометиях.

Выходные данные

Выведите единственное целое число — остаток от деления на $$$2022$$$ количества различных сбалансированных гласнометий, состоящих ровно из $$$N$$$ букв.

ПримерыВходные данные

1

Выходные данные

3

Входные данные

2

Выходные данные

20

Входные данные

3

Выходные данные

105

Входные данные

1234

Выходные данные

174

Примечание

Первый тестовый пример

Полный список сбалансированных гласнометий длины $$$1$$$: и, у, ү — в данных словах $$$0$$$ отверстий как на чётных позициях, так и на нечётных.

Второй тестовый пример

Полный список сбалансированных гласнометий длины $$$2$$$:

1. ии;
2. иу;
3. иү;
4. уи;
5. уу;
6. уү;
7. үи;
8. үу;
9. үү;
10. ээ;
11. аа;
12. ао;
13. аы;
14. оа;
15. оо;
16. оы;
17. ыа;
18. ыо;
19. ыы;
20. өө.

• В словах $$$1$$$ - $$$9$$$ на чётных и нечётных позициях по $$$0$$$ отверстий;
• В слове $$$10$$$ на чётных и нечётных позициях по $$$0.5$$$ отверстий;
• В словах $$$11$$$ - $$$19$$$ на чётных и нечётных позициях по $$$1$$$ отверстию;
• В слове $$$20$$$ на чётных и нечётных позициях по $$$2$$$ отверстия;

Третий тестовый пример

Некоторые из сбалансированных гласнометий длины $$$3$$$:

1. аөы — по $$$2$$$ отверстия;
2. эоэ — по $$$1$$$ отверстию;
3. иыа — по $$$1$$$ отверстию;
4. үиу — по $$$0$$$ отверстий.