矩阵快速幂求斐波那契数列第n项

#include<bits/stdc++.h>
using namespace std;
class rect {
	public:
		int width;
		int height;
		long long a[1000][1000];
		long long &mem(int x,int y) {
			return a[x-1][y-1];
		}
		void set(int x,int y) {
			width=x;
			height=y;
			for(int i=0; i<x; i++) {
				for(int j=0; j<y; j++) {
					a[i][j]=0;
				}
			}
		}
		rect operator*(rect x) {
			rect y;
			y.set(height,x.width);
			for(int i=0; i<height; i++) {
				for(int j=0; j<x.width; j++) {
					for(int k=0; k<width; k++) {
						y.mem(i,j)+=mem(k,j)*x.mem(i,k);
						y.mem(i,j)%=1000000007;
					}
				}
			}
			return y;
		}
		operator*=(rect x) {
			set(height,x.width);
			for(int i=0; i<height; i++) {
				for(int j=0; j<x.width; j++) {
					for(int k=0; k<width; k++) {
						mem(i,j)+=mem(k,j)*x.mem(i,k);
						mem(i,j)%=1000000007;
					}
				}
			}
		}
		operator=(rect x) {
			set(x.width,x.height);
			for(int i=0; i<height; i++) {
				for(int j=0; j<width; j++) {
					mem(i,j)=x.mem(i,j);
				}
			}
		}
};
rect fastpow(rect r,long long n){
	rect x=r;
	rect p;
	p.set(2,2);
	p.mem(1,1)=1;
	p.mem(2,1)=0;
	p.mem(1,2)=0;
	p.mem(2,2)=1;
	while(n!=0){
		if(n%2==1){
			p=p*x;
		}
		x=x*x;
		n/=2;
	}
	return p;
}
long long n=1;
int main() {
	cin>>n;
	rect r;
	r.set(2,2);
	r.mem(1,1)=1;
	r.mem(2,1)=1;
	r.mem(1,2)=1;
	r.mem(2,2)=0;
	cout<<(fastpow(r,n).mem(1,2));
	return 0;
}