fork download
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define N 101
  4. #define mod 1000000007
  5. using namespace std;
  6.  
  7. ll a[N][N] = {0},I[N][N];
  8. void mul(ll A[][N], ll B[][N], ll dim)
  9. {
  10. ll res[dim+1][dim+1];
  11. for (ll i = 0 ; i < dim; i++)
  12. {
  13. for (ll j = 0 ; j < dim; j++)
  14. {
  15. res[i][j] = 0;
  16. for (ll k = 0; k < dim; k++)
  17. {
  18. res[i][j] = ((res[i][j]) + (A[i][k] * B[k][j])%mod ) % mod;
  19. }
  20. }
  21. }
  22.  
  23. for (ll i = 0 ; i < dim; i++)
  24. {
  25. for (ll j = 0; j < dim; j++)
  26. {
  27. A[i][j] = res[i][j];
  28. }
  29. }
  30. }
  31. void power(ll A[][N], ll dim, ll n)
  32. {
  33. for (ll i = 0 ; i < dim; i++)
  34. {
  35. for(ll j = 0 ; j < dim;j++)
  36. {
  37. if (i == j)
  38. I[i][j] = 1;
  39. else
  40. I[i][j] = 0;
  41. }
  42. }
  43.  
  44. while(n > 0)
  45. {
  46. if(n % 2)
  47. {
  48. mul(I, A,dim);
  49. }
  50. mul(A,A,dim);
  51. n /= 2;
  52. }
  53.  
  54. for (ll i = 0 ; i < dim; i++)
  55. for (ll j = 0; j < dim; j++)
  56. A[i][j] = I[i][j];
  57. }
  58. int main()
  59. {
  60. ll n;
  61. cin >> n;
  62. for(ll i = 0;i < 6;i++)
  63. a[i][5] = 1;
  64. a[1][0] = 1;
  65. a[2][1] = 1;
  66. a[3][2] = 1;
  67. a[4][3] = 1;
  68. a[5][4] = 1;
  69.  
  70. power(a, 6, n-1);
  71. cout << 2 * a[1][0];
  72. return 0;
  73. }
  74.  
Success #stdin #stdout 0s 4256KB
stdin
Standard input is empty
stdout
1781709090