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 <= 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.


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