WC 4.2 - Are you Divisible?

You are given an integer(could be upto 100 digits)
You need to find the number of non-empty subsequences of this number that themselves are divisible by 2, 3 or 5
As the answer can be large give your answer modulo 1000000007

Read more about subsequences here

Note : 0 is divisible by every number
Note : A subsequence is different from another if it is of different size or the position(digit in the original number) of atleast one digit in it is different from the other subsequence
Note : Numbers with leading 0's are considered different subsequences and valid numbers
Eg : 0345, 00345 and 345 are considered different subsequences if they exist in the given number but all have same value of 345
Similarly, 0, 00, 000 are different subsequences and all have value 0

::Examples::
1) 111
Ans: 1
We can see that only 111 is divisible by 3
No other number formed by using the subsequences of this number is divisible by 3 or 5

2) 132
Ans : 5
There are total 7 subsequences of 132
But only some work : 3, 2, 32, 12, 132

3) 505
Ans : 7
All subsequences are valid : 5, 0, 5, 50, 55, 05, 505

4) 123456
Ans : 60

Solve for integer "23443639227874382376447553704910629585343332295513"


Click to view hint

This challenge is worth 80 points.

You must be logged in to submit a solution

View ranklist for this challenge
About scoring and submission

Contact Us


Krish Shah : 9323115454

Kaustubh Khavnekar : 9769408039



Privacy Policy