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.
The first and only line contains an integer n, denoting the length of integers.
The only line contains the answer modulo 9973.
1 <= n <= 109
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.
thanks, Lordxfastx, nice problem.Last edit: 2010-01-06 09:29:10