Problem 26306 --【递推】位数问题(例题)

26306: 【递推】位数问题(例题)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 15  Solved: 10
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][84kb]

Description

【例5位数问题


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

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


Input

Output

HINT

Source

[Submit][Status]