### PROBLEM LINK:

**Author:** Nikhil Khurana

**Tester:** Rahul Johari

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Multiplicative Inverse, DP, Maths.

### PROBLEM:

Given two distinct integers A and B, a number is called “lucky” if it contains only digits A and B. Another number is called “superlucky” if the sum of its digits is “lucky”.

For a given integer N (length of number), find how many superlucky numbers of length exactly N are there. Output the result modulo 10^{9}+7.

### EXPLANATION:

Let MOD = 1000000007. Let’s precalculate factorial values using modulo MOD.

Fact[i] = i! % MOD, Let i be an amount of digits equal to A in current superlucky number. In this case we can find sum of digits in this number as : sum = Ai + B(n-i).

If sum is lucky, then add C[N][i] to answer. In this problem it’s impossible to calculate binomial coefficients using Pascal’s triangle, because of large N. However it can be done this way

C[n][i] = fact[n]inv(fact[n - i]fact[i]).

Inv(a) is [multiplicative inverse element(modulo MOD)][5].

Observe that MOD is a prime number, so inv(a) = aMOD - 2. Calculating this values for each i from 0

to N will give correct answer in O(Nlog(MOD)).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.