fork download
copy 
  1. #include <stdio.h>
  2. #define MOD 1000000007ULL
  3.  
  4. unsigned long long a[2], temp[2], b[2][2], temp1[2][2], n;
  5.  
  6. void solve()
  7. {
  8. 	a[0] = 2;
  9. 	a[1] = 1;
  10. 	b[0][0] = 2;
  11. 	b[0][1] = 1;
  12. 	b[1][0] = 1;
  13. 	b[1][1] = 1;
  14. 	while(n>0)
  15. 	{
  16. 		if(n&1)
  17. 		{
  18. 			temp[0] = a[0]*b[0][0] + a[1]*b[1][0];
  19. 			temp[1] = a[0]*b[0][1] + a[1]*b[1][1];
  20. 			a[0] = temp[0]%MOD;
  21. 			a[1] = temp[1]%MOD;
  22. 		}
  23. 		temp1[0][0] = b[0][0]*b[0][0] + b[0][1]*b[1][0];
  24. 		temp1[0][1] = b[0][0]*b[0][1] + b[0][1]*b[1][1];
  25. 		temp1[1][0] = b[1][0]*b[0][0] + b[1][1]*b[1][0];
  26. 		temp1[1][1] = b[1][0]*b[0][1] + b[1][1]*b[1][1];
  27. 		b[0][0] = temp1[0][0]%MOD;
  28. 		b[0][1] = temp1[0][1]%MOD;
  29. 		b[1][0] = temp1[1][0]%MOD;
  30. 		b[1][1] = temp1[1][1]%MOD;
  31. 		n = n>>1;
  32. 	}
  33. }
  34.  
  35. int main()
  36. {
  37. 	unsigned int t;
  38. 	scanf("%u", &t);
  39. 	while(t--)
  40. 	{
  41. 		scanf("%lld", &n);
  42. 		n = n - 1ULL;
  43. 		solve();
  44. 		printf("%llu\n", (a[0]*a[1])%MOD);
  45. 	}
  46. }
Success #stdin #stdout 0s 2160KB
comments (?)
stdin
copy 
2
2
4
stdout
copy 
15
714
https://ideone.com/aQaNuu
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!