#
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**"

Solution explanation link : link

### This challenge is worth 80 points.

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

View ranklist for this challenge

About scoring and submission