该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面

在所有的$N$位数中，有多少个数中有偶数个数字$3$?由于结果很大，你只需要输出这个答案对12345取余的值。

输入格式

读入一个整数$N$。$(1 \leq N \leq 1000)$

输出格式

输出有多少个数中有偶数个数字$3$

样例 #1

样例输入 #1

2

样例输出 #1

73

提示

对于$20$%的数据，$1 \leq N \leq 6$