Mining Gold Field
All submissions for this problem are available.IIIT administration is always very hungry for money and they've now decided to mine their playground to look for hidden gold. Of course, they are very lazy and have handed it over to you as a part of Social Community service. You have $2$ types of mining bombs (in unlimited quantity) and you have to mine a row of size $1 * N$ (you can say $N$ cells), drawn on the ground (of course, other areas are mined by other students and their work will not affect your row, so you shouldn't be bothered with them). But the mining bombs are of very cheap quality, obviously as expected from the administration. - The 1st type of bombs mine only the cell they are dropped and the very next cell on the right. - The 2nd type of bombs mine only the cell they are dropped and the very next two cells on the right. You are not allowed to drop a bomb at a position which is already mined as the administration wants all gold for themselves and they think, if an area is mined twice the gold may be exposed and you may take some of it. Also, you cannot drop a bomb at a position if its mining range goes out of the $N$ cells, else it will affect the nearby hostels. You need to find the number of ways you can mine the row allotted to you with the given types of bombs. As the final answer may be too long, you are required to output the answer modulo 1000000007 ($10^9 + 7$). ###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - Each test case contains a single integer $N$. ###Output: For each testcase, output an integer in a new line, the number of ways you can mine the row modulo 1000000007. ###Constraints - $1 \leq T \leq 50$ - $1 \leq N \leq 5 * 10^8$ ###Sample Input: 2 5 1 ###Sample Output: 2 0 ###EXPLANATION: *For the 1st test case:* We have a row of 5 cells. So we can drop a bomb of 1st type in the 1st cell. As a result, cells 1 and 2 will be mined. Now we can drop a bomb of 2nd type in the 3rd cell. As a result, cells 3, 4 and 5 will be mined. Another way of mining is we can drop a bomb of 2nd type in the 1st cell. As a result, cells 1, 2 and 3 will be mined. Now we can drop a bomb of 1st type in the 4th cell. As a result, cells 4 and 5 will be mined. Thus we have total 2 ways to mine the row. *For the 2nd test case:* We have a row of 1 cell. So we can't drop any type of bomb as they will affect the area outside the cell too.
|Tags||aman_58472, bule18, dynamic-programming, easy-medium, fastmodexp|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions