Bob is creating an algorithm that can generate words. It works as follows:
Given an integer seed s:
For example, if s = 3705
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 106.
For each case output the number of valid words mod 109 + 7 on a single line.
3705
1001
505
1331
4224
552
86
8
13
23580