Inverse Digit Sum

Problem 684

Define to be the smallest number that has a digit sum of . For example .
Let
. You are given .
Further let be the Fibonacci sequence defined by and for all .
Find . Give your answer modulo .