//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "矩阵快速幂": {
        "prefix": "acm-1.3mksm",
        "body": [
            "#include <bits/stdc++.h>",
            "using namespace std;",
            "#define int long long",
            "const int N=3,mod=1e9+7;",
            "struct Matrix{",
            "\tint mat[N][N];",
            "\tMatrix(){memset(mat,0,sizeof(mat));}",
            "\tMatrix operator*(const Matrix& o)const{",
            "\t\tMatrix res;",
            "\t\tfor(int i=0;i<N;++i){",
            "\t\t\tfor(int k=0;k<N;++k){",
            "\t\t\t\tfor(int j=0;j<N;++j){",
            "\t\t\t\t\tres.mat[i][j]=(res.mat[i][j]+mat[i][k]*o.mat[k][j])%mod;",
            "\t\t\t\t}",
            "\t\t\t}",
            "\t\t}",
            "\t\treturn res;",
            "\t}",
            "};",
            "",
            "Matrix qpow(Matrix a,int b){",
            "\tMatrix res;",
            "\tfor(int i=0;i<N;++i)res.mat[i][i]=1;",
            "\twhile(b){",
            "\t\tif(b&1)res=res*a;",
            "\t\ta=a*a;",
            "\t\tb>>=1;",
            "\t}",
            "\treturn res;",
            "}"
        ],
        "description": "插入 矩阵快速幂"
    }
}