Google | Amazon | Number of Ways
Anonymous User
253

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

Comments (3)