5329: 【递推】位数问题（例题）

【例5】位数问题

【问题描述】      在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。 【输入格式】      读入一个数N 【输出格式】      输出有多少个数中有偶数个数字3。 【输入样例】      2 【输出样例】      73 【数据规模】      1<=N<=1000 【样例说明】

     在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个