题面

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

2

样例输出 #1

73

提示

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