Banta needs help
All submissions for this problem are available.
As we all know that Santa and Banta are good friends and they use to tease each other by giving mathematical questions to each other . So one day Santa has designed a problem for Banta . What Banta has to do is to count total number of chocolates , and the chocolate distribution is as follows ,
There are N students whom chocolate is to be distributed . Santa aligned each student in a line according to the marks in decreasing order and then start giving chocolates one by one to each student .
The first student will get f(1) number of chocolates .
The second student will get 2*f(2) number of chocolates .
The third student will get 3*f(3) number of chocolates .. and so on
so the Nth student will get n*f(n) number of chocolates .
f(x) is defined as
f(x) = 1 if x=1 or x =2
f(x) = f(x-1) + f(x-2) for all x > 2
As we all know that Banta is not very good at Maths so he needs your help , So help Banta by counting the total number of chocolates required . Since the answer can be very large print it Modulo 1000000007 . .
The first line of input contains T denoting the number of test cases. In every test case, Value of N will be given in a single line .
For every test case print the total number of chocolates required in a new line.
Should contain all the constraints on the input data that you may have. Format it like:
- 1 ≤ T ≤ 10^5
- 1 ≤ N ≤ 10^9
Subtask #1 (20 points), Time limit : 1 sec 1 ≤ T<=100000, N<=10^6
Subtask #2 (80 points), Time limit : 1 sec 1 ≤ T<=100000, N<=10^9
Input: 3 1 2 4
Output: 1 3 21
Testcase 1 : only 1 student is there and the total number of chocolates required is f(1) =1 . Testcase 2 : 2 students are there thus total number of chocolates required is 1* f(1) + 2*f(2) = 1*1 + 2*1 = 3 . Testcase 3 : 3 students are there thus total number of chocolates required is 1* f(1) + 2*f(2) + 3*f(3) = 1*1 + 2*1 + 3*2 + 4*3 = 21 .
|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, 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