How we can find large Pell Number and its modulus in efficient way?
Problem 4: The Price of Death
Robert Baratheon, King of the Seven Kingdoms, is very insecure. He had led the rebellion which smashed the might of the previous king, Aerys (II) Targaryen (the Mad King). After the Mad King’s death, his wife gave birth to Daenerys who was then smuggled across the narrow sea to Pentos. Robert has now come to know of her existence and seeing that she holds a better claim to the Iron Throne, conspires to assassinate her. He thinks of hiring a Faceless Man to do the job. Little does he know of the price he would have to pay.
The Faceless Man assures that the execution will be a success but provides no definite time guarantees. For the nth minute he spends in Robert’s service, his price in silver coins is the sum of: the number of silver coins he earned the previous minute, twice those he earned two minutes before, thrice those he earned three minutes before and (once) those he earned four minutes before. For the first four minutes, his prices are 1, 2, 5 and 12 coins; the cost for the fifth minute is hence, 29. As payment he asks for the silver coins he earned in the Nth minute, where N is the number of minutes he is in Robert’s service. Since Robert does not know how much time the Faceless Man will take, he decides to find the cost for some values of N. Given this value, find the cost of the assassination modulo 10^9 + 7. Input :
First line an integer Q number of queries . Each of the following Q lines contains a integer N. Output :
For each query output an Integer which denote cost of assassination for Nth minute modulo 10^9 + 7 . Constratints :
1 <= Q <= 52000 1 <= N <= 10^18 Sample Input :
5
1
2
5
100
1000
Sample Output:
1
2
29
852799803
671754329
Source — IIT kharagpur Bitwise Programming Contest 2013
Full text and comments »