Statement is not available in English language
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$$$ отверстий.