prefix-numbers

Areesha likes to play interesting games with her friend Adam.
The game they played last evening is about building a number with n digits.

They start with a number without any digits.
There will be n moves.
In each move players append one digit to a number — so a new digit will be the last digit after the move.
The only rule is: after every appended digit, the number has to be divisible by this digit.
It implies that they can never add a digit 0.

Adam thinks the game is easy, because there are many numbers they can get at the end.
But how many are there?
Count numbers they can get, modulo 2^{32}.

Input format
The only line of the input contains one integer n — the number of times players will append a digit.

Output format
Print the number of numbers Adam and Areesha can get, modulo 2^{32}.

Constraints

1 ≤ n ≤ 10^{18}

SAMPLE INPUT
2

SAMPLE OUTPUT
41

Explanation

For n = 2 there are 41 possible numbers:
$11, 12, 15, 21, 22, 24, 25, 31, 32, 33, 35, 36, 41, 42, 44, 45, 48, 51, 52, 55, 61,$
$62, 63, 64, 65, 66, 71, 72, 75, 77, 81, 82, 84, 85, 88, 91, 92, 93, 95, 96, 99$

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Matrices


Solutions:
import numpy as np
name = input()
_n_ = int(name)
LN = 4*7*9
vec = [[0 for j in range(10)] for i in range(LN)]
isDigitLegal = [[False for j in range(10)] for i in range(LN)]

alwaysCanAddDigit = [False, True, True, False, False, True, False, False, False, False]
whatMod =   [0, 0,0,3, 2,0,3, 0,0,0]
multIndex = [0, 0,0,2, 0,0,2, 1,0,2]
def canAddDigit(j, digit):
	return alwaysCanAddDigit[digit] or (whatMod[digit] != 0 and j[multIndex[digit]] % whatMod[digit] == 0) or j[multIndex[digit]] == 0


MOD = 2**32
def mult(a, b):
	return int(a*b) % MOD
def mypow(a, b):
	res = 1
	while b > 0:
		if b % 2 != 0:
			res = mult(res, a)
		a = mult(a,a)
		b = int(b/2)
	return res	


for i in range(4):
	for j in range(7):
		for k in range(9):
			for n in range(1, 10):
				vec[i*63+j*9+k][n] = ((i*2+n)%4)*63 + ((j*3+n)%7)*9 + ((k+n)%9)
				jj = (i, j, k)
				isDigitLegal[i*63+j*9+k][n] = canAddDigit(jj, n)
				
mat = np.zeros([LN,LN], dtype=int)
for i in range(LN):
	for j in range(1, 10):
		if isDigitLegal[i][j]:
			mat[vec[i][j], i] += 1
newVec = np.zeros([LN], dtype=int)
newVec[0] = 1
W,V = np.linalg.eig(mat)
#print (np.array((V*W).dot(np.linalg.inv(V))).astype(int) != mat).sum()
for i in range(LN):
	W[i] = mypow(W[i], _n_)


print((int(np.linalg.matrix_power(mat, _n_).dot(newVec).sum()) % MOD))