#!/usr/bin/env python3

import math

def multinomial(n, digits=7):
    n=str(n).zfill(digits)
    temp={}
    for i in n:
        if not i in temp:
            temp[i]=0
        temp[i]+=1
    out=math.factorial(digits)
    for i in temp:
        out//=math.factorial(temp[i])
    return out

def Memoize(func):
    cache={}
    def inner(n):
        n=scrub(n)
        if not n in cache:
            cache[n]=func(n)
        return cache[n]
    return inner

def square_digit_sum(n):
    n=str(n)
    return sum(int(i)**2 for i in n)

def scrub(n):
    n=[i for i in str(n) if not i=="0"]
    n.sort()
    return int("".join(n))

@Memoize
def arrives_at_89(n):
    while True:
        if n==1:
            return False
        elif n==89:
            return True
        n=square_digit_sum(n)

def wrapper(n):
    n=square_digit_sum(n)
    return arrives_at_89(n)

def pre_requisites(n):
    a=int(n**0.5)
    for i in range(1,a+1):
        if ((n-i**2)**0.5).is_integer():
            print(i,int((n-i**2)**0.5))

def main(upper=7):
    count=0
    cache={}
    for i in range(1, 10**upper):
        i=scrub(i)
        if not i in cache:
            if wrapper(i):
                count+=multinomial(i, upper)
            cache[i]=None
    return count
