All Tracks Problem

Divisible by 15 - Part 2
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

You are provided with a big number N( a string of digits ) .
You need to find the number of ways to partition it into strings such that every partitioned string of number is divisible by 15.
Note that no partitioned string should start with leading zeroes (although the partitioned number can be 0 itself).
Print Answer Modulo \(10^{9}\)+7

Input Format:-
First Line will contain an integer T denoting the number of test cases.
Each test case will contain one string, i.e. the big integer N.

Output Format:-
Output the answer in new line for each test case.

Constraints:-
1 ≤ T ≤ 100
1 ≤ length of string (N) ≤ \(10^{5}\)
Sum of N over all test cases ≤ \(10^{5}\)

SAMPLE INPUT
2
15015
150
SAMPLE OUTPUT
3
2
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

National Institute of Technology Jalandhar

Challenge Name

Sprint Challenge 1

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?