nTrip = 2
steps = 10

countTable = [([1]+[0] * nTrip) for j in range(steps+1)]
countTable[0] = [1]*(nTrip+1)
for i in xrange(1, steps+1):
	for j in xrange(1, nTrip+1):
		s1, s2 = 0, 0
		if j > 0:
			s1 = countTable[i][j-1]
		if i >= 3**(j-1)*2:
			s2 = countTable[i-3**(j-1)*2][j]
		countTable[i][j] = s1 + s2

def calc(t, mult=1):
	if mult == 0:
		return []
	valList = []
	for x in xrange(1, 3**t):
		if (x*mult) % 3 == 1:
			if t == 1:
				return [[x]]
			for y in calc(t-1, (x*mult-1)/3):
				valList.append([x]+y)
	return valList

def to2Cycle(t):
	if len(t) == 0:
		return []
	for x in xrange(0, 3**(len(t)-1)*2):
		if (2**x)%(3**len(t)) == t[0]:
			return [x] + to2Cycle(t[1:])
	return -1

def count(t, m):
	if t == []:
		return 1
	size = len(t)
	for x in t:
		m -= x
	m -= size
	return countTable[m-1][size]

sum = 1
for x in range(1, nTrip+1):
	for pattern in map(to2Cycle, calc(x)):
		print pattern
		print count(pattern, steps)
		sum += count(pattern, steps)
		if pattern[0] == 2:
			sum -= count(pattern[1:], steps-3)
print sum