Kisses & Hugs
All submissions for this problem are available.
Princess Artapoelc greeted her guests by either kissing on the cheek (K) or hugging (H). From the first guest
she kisses, she has a
compulsion to necessarily kiss every alternate guest from that first kissed guest. That is if the guests are G1,
G2, ..., Gi, Gi+1, ..., Gn and if she first kissed Gi then she must necessarily kiss
Gi+2, Gi+4, Gi+6 ... till the last
possible guest. Your task is to determine in how many ways she can greet N guests.
First line of the input contains T (T ≤ 1000) denoting the number of test cases.
lines follow each containing a single integer N (1 ≤ N ≤ 10^9) denoting the number of guests.
For each case the output should be a single integer representing the number of ways Artapoelc can greet N guests. As the
answer can be large
print it modulo 1000000007.
3 1 2 3
2 4 6
In the first case the possible ways are
KH, HK, HH, KK
HHH, HHK, HKH, HKK, KHK, KKK
|Tags||exponentiation, kaushik_iska, maths, matrix-expo, sep12|
|Time Limit:||0.190821 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.