題目鏈接：http://codeforces.com/problemset/problem/185/A
Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". This plant has an amusing feature. After one year a triangle plant directed "upwards" divides into four triangle plants: three of them will point "upwards" and one will point "downwards". After another year, each triangle plant divides into four triangle plants: three of them will be directed in the same direction as the parent plant, and one of them will be directed in the opposite direction. Then each year the process repeats. The figure below illustrates this process.
Help the dwarfs find out how many triangle plants that point "upwards" will be in n years.
The first line contains a single integer n (0?≤?n?≤?1018) ― the number of full years when the plant grew.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64dspecifier.
Print a single integer ― the remainder of dividing the number of plants that will point "upwards" in n years by 1000000007 (109?+?7).
The first test sample corresponds to the second triangle on the figure in the statement. The second test sample corresponds to the third one.
PS:
上3角個數：△-> 3*△ +1*
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
