# Number of ways to make n digit number?

Given M digits which are between 1 to 9, Find the number of ways to form N digit number, by repeating one or more given digits such that each of M digits are present in N digit number at least once. Example if M = 3 and N = 4 Answer is 36.

Explanation - let the three digits be 1 2 3 our N = 4, digit number can be 1123, 3211, 1132, ..... repeating 1 similarly repeating 2 and three we will get the total ans.

Since answer is large find the ans % 10000000007. 1 ≤ M ≤ N ≤ 100.

• Is this a project Euler problem? – rogerl Oct 2 '14 at 23:26
• nope its from a contest that was held in September, code.google.com/codejam/contest/4214486/dashboard#s=p0 – Ashesh Vidyut Oct 2 '14 at 23:28
• For each specific case (at least small ones) I'd recommend inclusion-exclusion. However, I am not too familiar with coding contest problems, so I don't know what methods would work well there (you'd need to handle more general cases, but you have more number-crunching ability compared to the common by-hand problem) – Arthur Oct 2 '14 at 23:35
• Do the repeated digits have to be adjacent? In your examples, you include 1123 and 3211, but not for example 1231. – rogerl Oct 2 '14 at 23:45
• Non mathematical way would be dp+bitmask. the dp is like plugging characters to the right and setting on the digits that have been used. That assuming that M<10. – Phicar Oct 3 '14 at 2:21

If I understand this correctly it is a familiar problem, equivalent to the problem of counting the number of $N$-letter words from an alphabet of size $M$, with the restriction that each letter is used at least once.
The well-known answer is $M!S(N,M)$, where $S(N,M)$ is the Stirling number of the second kind, counting the number of ways to partition $[N]$ in $M$ parts. You can find references about these Stirling numbers like recursive formulas and generating functions all over the place if you actually need to write a program that produces the answer for concrete values of $M$ and $N$.
Btw, a Java implementation using a simple summation for these Stirling numbers calculates e.g. $S(200,100)$ in a fraction of a second (although it has over 200 digits), so performance cannot be a problem for the values you mention.