Count Digit Strings With a Given Remainder

You are given a (potentially huge) integer length and two integers modulus and remainder.

Consider all strings of exactly length digits where:

• every digit is 1, 2 or 3;
• the substring "12" never appears, meaning a 1 is never immediately followed by a 2;
• the string, read as a base-10 integer, leaves remainder remainder when divided by modulus.

Return the number of such strings. Mod the result by $10^9 + 7$.

Examples

Example 1

Input: length = 2, modulus = 2, remainder = 0
Output: 2
Explanation: The length-2 strings avoiding "12" are 11, 13, 21, 22, 23, 31, 32, 33. Of these, 22 and 32 are even.

Example 2

Input: length = 2, modulus = 3, remainder = 1
Output: 3
Explanation: 13, 22 and 31 leave remainder 1 when divided by 3.

Example 3

Input: length = 3, modulus = 5, remainder = 2
Output: 5
Explanation: Since 10 and 100 are divisible by 5, only the last digit matters, and it must be 2. The qualifying strings are 132, 222, 232, 322 and 332. (122 also ends in 2 but contains "12", so it is excluded.)