Hi, had this question for today's assesment. Kind of frustated, not being able to solve it. Please share your thoughts !
Given a string G consisting of digits from 0 to 9. However, your friend replaced all occurences of digit '5' by '33' and all occurences of digit '9' by '77' and changed it to a new string S.
Now you have forgotten the original string G. However, you have the string S which was modified by your friend. Find the total number of possible values of G that could result in S. The answer could be possibly very large, so return answer modulo 1e9+7.
Constraints :
N => Length of String => 10^5
Example:
Input:
333
Output:
3
Explanation:
35, 53, 333
Input:
335
Output:
2
Explanation:
55, 335
Input:
7733
Output:
4
Explanation:
933, 775, 95, 7733