# 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

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"

### You must be logged in to submit a solution

View ranklist for this challenge