Chef and Dishes
All submissions for this problem are available.
Chef buys a new restaurant. At his new restaurant, he calls his rival chef named 'Code'. Also he places all his dishes on N different tables in
such a order that, the
first table contains dish "a" and second one contains dish "b". From next table onwards dishes are arranged in such a way that, the dish on the given
table is the mixture of the
previous two table's dishes, i.e., the dishes on table 1, 2, 3, 4, 5, 6 will be "a", "b", "ba", "bab", "babba", "babbabab" respectively and so on.
Code goes to Kth table and performs m queries on the dish at that table to annoy chef.
On each query he picks up a different section si of the dish and asks chef, the number of occurrences of si in the given dish.
- The first line contains two space-separated integers K and m denoting the table number and the number of queries, correspondingly.
- Next m lines contain sections si that correspond to the queries. It is guaranteed that section si isn't empty and consist only of
characters "a" and "b".
- For each section si print the number of times it occurs in the dish on the given table. Since the numbers can be large enough, print them
modulo 1000000007 (10^9+7). Print the answers for
the section in the order in which they are given in the input.
- 1 <= K <= 1018
- 2 <= m <= 104
- The total length of strings si doesn't exceed 10^5
Input: 6 5 a b ab ba aba Output: 3 5 3 3 1 Input: 10 10 bb ab ba aa bb ab ba aa bb ab Output: 12 21 21 0 12 21 21 0 12 21
Case 1 : Code goes to table number
6, which contain babbabab as the dish. Section 'ba' has occurred 3 times in the given dish. Similarly aba has occured once in the given dish.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.