记录编号	308352	评测结果	AAAAAAAAAA
题目名称	[Codeforces 712C] 三角恒等变换	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-09-17 16:59:53	内存使用	0.00 MiB

#include <cstdio>
#include <iostream>
using namespace std;
const int MOD = 1000000000+7;
long long ans,h,l,r;
inline int fast_mod(int n)
{
    int t[2][2] = {1, 1, 1, 0};
    int ans[2][2] = {1, 0, 0, 1};
    int tmp[2][2];

    while(n)
    {
        if(n & 1)
        {
            for(int i = 0; i < 2; ++i)
                for(int j = 0; j < 2; ++j)
                    tmp[i][j] = ans[i][j];
            ans[0][0] = ans[1][1] = ans[0][1] = ans[1][0] = 0;

            for(int i = 0; i < 2; ++i)
            {
                for(int j = 0; j < 2; ++j)
                {
                    for(int k = 0; k < 2; ++k)
                        ans[i][j] = (long long)(ans[i][j] +(long long) tmp[i][k] * t[k][j]) % MOD;
                }
            }
        }

        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j)
                tmp[i][j] = t[i][j];
        t[0][0] = t[1][1] = 0;
        t[0][1] = t[1][0] = 0;
        for(int i = 0; i < 2; ++i)
        {
            for(int j = 0; j < 2; ++j)
            {
                for(int k = 0; k < 2; ++k)
                    t[i][j] = (long long)(t[i][j] +(long long)tmp[i][k] * tmp[k][j]) % MOD;
            }
        }
        n >>= 1;
    }
    return ans[0][1];
}
int MAIN()
{
    freopen("Triangulartransformation.in","r",stdin);
    freopen("Triangulartransformation.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    if(m==0)
    {
        printf("%d %d",n,n);return 0;
    }
    if(m==2||m==1)
    {
        printf("-1");return 0;
    }
    h=fast_mod(m);
    r=h*n-h+1;r%=MOD;
    h=fast_mod(m-1);
    l=h*n-h+2;l%=MOD;
    cout<<l<<" "<<r;
    return 0;
}
int main(){;}
int EZOI=MAIN();