在所有的N位正整数（1位数不包含0）中，有多少个数中有偶数（0也是偶数）个数字3？

读入一个数N。1<=N<=1000。

一个整数，表示答案。
注意：0个3也是偶数个3，但是1位数里不包含0.
由于结果可能很大，你只需要输出这个答案mod 12345的值。

input
output

时间限制：1s
空间限制：256MB