The Dirty Experiment
Mr Vicky is conducting an experiments on shrimps. He puts a number of beakers in a row numbered from 1 to N. He places 1 shrimp in the first beaker. Then he adds the number of shrimps in this beaker to the next two beakers. Formally, he adds the number of shrimps in beaker i to beaker i+1 and i+2 without removing any from i. This action is performed for beakers upto N-1 such that his N beakers are filled.
Experiments can be performed on a beaker j of capacity Sj, if and only if there exists another beaker k, (2 < k < j) of capacity Sk such that Sj = n*Sk, where n is any positive integer.
The capacity of each beaker is the maximum number of shrimps it can contain which in turn equals the number of shrimps Mr. Vicky had added earlier.
Given a number B representing the number of beakers numbered 1,2,.. upto B, find the number of beakers A1 that are ready for experiments.
Now there is one more query that comes to Mr. Vicky's mind.
Mr. Vicky has 4 species of shrimps- Calman, Haworth, Dana and Smith. These have a unique way of expanding their species. Each species follow a transformation pattern with each species transforming into 1 or more species after every 1 second. This pattern is static and does not change with time.
At the beginning (t=0) Mr. Vicky starts with a Calman. The number of different species of shrimps that Mr. Vicky obtains for the next 5 seconds as a result of the transformation of each species is as under.
At t=1 sec, he has 1 Haworth,
At t=2 sec, 1 Smith and 1 Dana,
At t=3 sec, 1 Calman, 2 Haworth and 2 Smith,
At t=4 sec, 3 Haworth, 4 Smith and 2 Dana,
At t=5 sec, 2 Calman, 6 Haworth, 9 Smith and 3 Dana and so on..
Given a time T you have to tell Vicky the number of Calman(A2), number of Haworth(A3) number of Smith(A4) and number of Dana(A5) in the tank.
The input begins with the number of test cases C. Then C cases follow each of a single line, containing two integers B and T, the beakers numbered 1 to B, and T the time(in sec) elapsed after the start of the experiment.
Print a total of C lines, a single line for each test case containing 5 space separated integers A1, A2, A3, A4 and A5.
As these numbers can be quite large print Ai modulo 1000000000000007(10^15+7). i=1, 2, 3, 4, 5
1 <= C <= 100000 0 <= B <= 201200 0 <= T <= 201200
Input: 3 1 1 2 2 3 3 Output: 0 0 1 0 0 0 0 0 1 1 0 1 2 2 0 Explanation: Considering the 3rd case, Clearly the three beakers have 1, 1 and 2 shrimps with no pair of (j, k) such
that Sj = n*Sk. Hence beakers ready for experiment is 0. Also after 3 seconds, Vicky has
1 Calmon, 2 Haworth and 2 Smith as given in the problem statements itself.
|Time Limit:||0.23431 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, GO|
Fetching successful submissions