time limit per test: 0.25 sec.
memory limit per test: 4096 KB
For given number N you must output amount of N-digit numbers, such, that last digits of their square is equal to 987654321.

Input

Input contains integer number N (1<=N<=106)

Output

Write answer to the output.

Sample Input

8

Sample Output

题解：

我们通过打表可以发现
当n小于9时，没有数可以满足。
当n等于9时，有8个数：
111111111
119357639
380642361
388888889
611111111
619357639
880642361
888888889
当n等于10时，我们可以发现，除了后九位的数以外，均对答案无影响，所以第十位上可以选9个，不能为0.
所以往后推得时候，我们可以发现，第一位一定是9中选择，而第二位往后到不是后九位的位上都有10种选择。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int main()
{
    int n;
    cin >> n;
    if (n < 9)
        puts("0");
    else if (n == 9)
        puts("8");
    else
    {
        cout << 72;
        for (int i = 1; i <= n-10; i++)
            printf("0");
    }
    return 0;
}