7. Telefonát

“Čau Radka, už si sa začala učiť na maturity?” ozvalo sa zo slúchadla.

“Blázniš?! Však je polka leta. Aktuálne ma trápi iba to, ako budem čo najdlhšie spať, a kde sa pôjdem kúpať.”

“No hej… Ale vieš, že tohtoročné maturity pripravuje Žaba. To nebude také ľahké. A ak chceš aby ťa zobrali na informatiku na najlepšej škole – matfyze¹ – bez prijímačiek, musíš mať z maturity 1.”

“Prosím ťa. Na to aby ťa zobrali na matfyz stačí byť úspešným riešiteľom olympiády v informatike, teda získať 10 zo 40 bodov. Malina. A ešte sa na dva dni uleješ zo školy. Aj ty by si sa mala tento rok zapojiť, Rebeka.”

“Okrem toho,” pokračovala Radka, “videla som jedno z nových maturitných zadaní. Spočítaj ciferný súčet zadaného čísla². Mala som to naprogramované za 3 minúty. Však pozri, poslala som ti kód v správe.”

“Počuj, Radka,” opáči Rebeka. “Určite to máš dobre? Však tam máš * namiesto +.”

“Ale však na všetkých vstupoch to fungovalo. Pre 22 vráti 4. Pre 1142 číslo 8…”

“No hej, ale mám pocit, že to je skôr náhoda. Však pre 33 vypíšeš 9, ale správne by to malo byť 6.”

“Hmmm… máš pravdu. Ale aj tak, skúšala som si to na fakt veľa vstupoch a vždy to dávalo správne výsledky.”

“Asi preto, že sa ti vždy podarilo trafiť číslo, ktorého ciferný súčet aj súčin sú rovnaké. Mala si len šťastie, alebo je takých čísel ozaj tak veľa?” zaujímalo Rebeku.

“Neviem, ale určite sa to dá vypočítať!”

Úloha

Samozrejme, čísel, ktoré majú rovnaký ciferný súčet aj súčin je nekonečne veľa. A ak to samozrejmé nie je, tak si to skúste rozmyslieť. Zistovať ich počet by preto nebola zaujímavá KSP úloha. Zaujímavé je ale zisťovať, koľko prirodzených čísel má ciferný súčet aj súčin rovný číslu \(n\).

Formát vstupu

Na jedinom riadku vstupu je zadané číslo \(n\). V ôsmych testovacích sadách platia pre toto číslo nasledovné obmedzenia:

Formát výstupu

Na výstup vypíšte jedno číslo – počet prirodzených čísel, ktorých ciferný súčet aj ciferný súčin je rovný číslu \(n\). Keďže takýchto čísel môže byť naozaj veľa, vypíšte ich počet modulo \(10^9 + 7\).

Príklad

Input:

4

Output:

2

Dve čísla, ktorých ciferný súčet aj súčin je 4 sú čísla 22 a 4.

Input:

8

Output:

23

Jednou z možností je číslo 1142.

Input:

72

Output:

100110164