链接：

来源：牛客网

 

题目描述

精通程序设计的 Applese 叕写了一个游戏。

在这个游戏中，有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大，你需要将答案对 109+7109+7 取模。

输入描述:

仅一行两个正整数 n, m，表示方阵的大小。

输出描述:

输出一个正整数，表示方案数对 109+7109+7 取模。

示例1

输入

复制

1 1

输出

复制

2

示例2

输入

复制

2 2

输出

复制

4

备注:

1≤n,m≤10^100000

思路：思路很简单，就是2的n次方膜1e9+7，但是我们有个问题，就是数据的问题，10^100000，数据太大，我们就可以用欧拉降幂，基本板子题   

代码：

#include 
    
     #define ll long long int #define mod 100000007using namespace std;char a[100005];char b[100005];ll x,z=mod;ll quickpow(ll x,ll y,ll z){    ll ans=1;    while(y)    {        if(y&1)            ans=ans*x%z;        x=x*x%z;        y>>=1;    }    return ans;}ll phi(ll n){    ll i,rea=n;    for(i=2;i*i<=n;i++)    {        if(n%i==0)        {            rea=rea-rea/i;            while(n%i==0)                n/=i;         }    }    if(n>1)        rea=rea-rea/n;    return rea;}int main(){    while(scanf("%s %s",a,b)!=EOF)    {        ll len=strlen(a);        ll p=phi(z);        ll ans=0;        for(ll i=0;i