404242: GYM101466 G Generative Model

Bob is creating an algorithm that can generate words. It works as follows:

Given an integer seed s:

1. Create a list A from the prime factors of s: For example, if s = 240, then A = [3, 2, 2, 2, 5, 2].
2. Concatenate all the digits from A into a string B.
3. Repeat the following process while B is not empty: Remove a digit x from B or create a new number x by removing two elements of B and concatenating them. Turn each x into an english lowcase letter: this is done assuming that the english alphabet is 1-indexed, for example: 1 = a, 2 = b, 3 = c, ... 26 = z. Obviously, x must satisfy that 1 ≤ x ≤ 26.
4. Finally, concatenate all the letters into a single word.

For example, if s = 3705

1. A = [19, 13, 3, 5]
2. B = "191335"

From B we can generate "mico" as follows: [13, 9, 3, 15] = [m, i, c, o]

From B we can also generate "kecci" as follows: [11, 5, 3, 3, 9] = [k, e, c, c, i]

Please note that when doing the words-number trailing zeroes are not allowed. For example, 02 does not correspond to b.

Alice thinks that Bob's model is very poor and that in fact, it can't generate words that belongs to any language. Bob is very confident about his model, that's why he wants to write a program that given s computes how many words can be generated. As Bob knows you are training to participate on the ACM - ICPC World Finals, he wants you to write a program that counts the possible words.

There will be multiple cases. Each line contains a positive integer s less than 10⁶.

For each case output the number of valid words mod 10⁹ + 7 on a single line.

3705
1001
505
1331
4224

552
86
8
13
23580