Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <random>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef double ld;
- #define int ll
- typedef vector<char> vc;
- typedef vector<vc> vvc;
- typedef vector<vvc> vvvc;
- typedef pair<int, int> pii;
- typedef pair<pii, pii> piii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<pii> vpi;
- typedef vector< vi > vvi;
- typedef vector< vvi > vvvi;
- typedef vector<short> vs;
- typedef vector<vs> vvs;
- typedef vector<vvs> vvvs;
- typedef vector<ll> vl;
- typedef vector<vl> vvl;
- typedef vector<vvl> vvvl;
- typedef vector<ld> vld;
- typedef vector<vld> vvld;
- typedef vector<vvld> vvvld;
- typedef vector<string> vst;
- typedef vector<vst> vvst;
- typedef pair<ld, ld> pld;
- #define inmin(a, b) a = min(a, (b))
- #define inmax(a, b) a = max(a, (b))
- #define ALL(a) a.begin(),a.end()
- #define RALL(a) a.rbegin(),a.rend()
- #define sqr(x) ((x) * (x))
- #define fori(i, n) for(int i = 0; i < int(n); ++i)
- #define SZ(a) ((int)((a).size()))
- #define triple(T) tuple<T, T, T>
- #define quad(T) tuple<T, T, T, T>
- #define watch(x) cerr << (#x) << " = " << (x) << endl;
- #ifdef RUS_HOME
- #define cerr cout
- #else
- #define cerr if (false) cerr
- #endif
- const double PI = 2 * acos(0.0);
- #define rand shittttty_shit
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
- const string DIGITS = "0123456789";
- const string ALPH = "abcdefghijklmnopqrstuvwxyz";
- template <class T0, class T1>
- inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
- return out << "{" << a.first << ", " << a.second << "}";
- }
- template <class T0, class T1>
- inline istream & operator >> (istream &in, pair<T0, T1> &a) {
- return in >> a.first >> a.second;
- }
- template <class T0, class T1, class T2>
- inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
- return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
- }
- template <class T0, class T1, class T2, class T3>
- inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
- return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " << get<3>(a) << "}";
- }
- template<class T>
- inline ostream & operator << (ostream &out, vector<T> &a) {
- out << "[";
- fori (i, a.size())
- out << a[i] << vector<string>{", ", "] "}[i + 1 == a.size()];
- return out;
- }
- void smain();
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- #ifdef RUS_HOME
- freopen("input", "r", stdin);
- clock_t start = clock();
- #endif
- cout << setprecision(12) << fixed;
- smain();
- #ifdef RUS_HOME
- cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) / CLOCKS_PER_SEC << endl;
- #endif
- return 0;
- }
- const int N=2e3+100,MOD=1e9+7;
- vvi mult(vvi a, vvi b){
- int n=SZ(a);
- int m=SZ(b[0]);
- int k=SZ(b);
- vvi c(n,vi(m));
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++){
- for(int l=0;l<k;l++){
- c[i][j]=(c[i][j]+a[i][l]*b[l][j])%MOD;
- }
- }
- }
- return c;
- }
- vvi pow(vvi a, int n){
- vvi c={{1,0,0},{0,1,0},{0,0,1}};
- while(n){
- if(n&1)
- c=mult(c,a);
- a=mult(a,a);
- n>>=1;
- }
- return c;
- }
- vvi kek={{1,2,1},{1,0,0},{0,1,0}};
- void smain() {
- int n;
- cin>>n;
- if(n==1){
- cout<<1;
- return;
- }
- vvi d={{1,0,0}};
- vvi a=mult(d,pow(kek,n+1));
- //vvi b=mult(d,pow(kek,n));
- //vvi c=mult(d,pow(kek,n-2));
- cout<<(a[0][0])%MOD;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement