LPRIME - Primes of Lambda
Lambda checks primality in a weird way. He checks the following two conditions.
- All the digits of the number in the decimal system are primes or one, namely 1, 2, 3, 5 or 7.
- It isn't a multiple of 2, 3, 5, 7, 11 or 47 (Why 47? I don't know).
In order to estimate the accuracy of his approach, he asks you to calculate the number of decimal integers of a specific length that satisfy the conditions.
Input
The first and only line contains an integer n, denoting the length of integers.
Output
The only line contains the answer modulo 9973.
Example
Input:
1
Output:
1
Input:
2
Output:
8
Input:
4
Output:
182
Input:
1000000000
Output:
4589
Constraints
1 <= n <= 10^{9}
In 50% of testcases, n <= 100
Note: Data corrected and solutions rejudged. Sorry for inconvenience.
Warning: A naive solution won't terminate in 30s. And be careful with certain languages.
hide comments
Oleg:
2009-12-29 13:31:39
thanks, Lordxfastx, nice problem. Last edit: 2010-01-06 09:29:10 |
Added by: | Lox |
Date: | 2009-12-28 |
Time limit: | 1s-2.103s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | Own problem |