Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef unsigned long long ull;
- void power(ull F[2][2], ull n);
- void multiply(ull F[2][2], ull M[2][2]);
- const ull MOD = 1000000007;
- ull solve(ull n)
- {
- if (n==0) return 0;
- ull F[2][2] {{1, 1}, {1, 0}};
- power(F, n-1);
- return F[0][0];
- }
- void power(ull F[2][2], ull n)
- {
- if (n==0 or n==1) return;
- ull M[2][2] {{1, 1}, {1, 0}};
- power(F, n/2);
- multiply(F, F);
- if (n%2!=0)
- multiply(F, M);
- }
- void multiply(ull F[2][2], ull M[2][2])
- {
- ull x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
- ull y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
- ull z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
- ull w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
- F[0][0] = x%MOD;
- F[0][1] = y%MOD;
- F[1][0] = z%MOD;
- F[1][1] = w%MOD;
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
- ull n; cin >> n;
- cout << solve(n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement