Submission #70881034

---

Source Code Expand

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pn putchar(10)
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<int,int>
#define pdi pair<ll,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define Fo(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define reg register
#define eb emplace_back
#define bct __builtin_popcount 
#define mk make_pair
#define IT iterator
#define all(x) x.begin(),x.end()
#define lbd lower_bound
#define ubd upper_bound
#define lowbit(x) (x&(-x))
#define gb(x,i) ((x>>i)&1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
// #pragma GCC optimize(2)
using namespace std;

typedef int32_t i32;
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef double db;

// typedef int ll;
typedef long long ll;
// typedef __int128 ll;
const ll mod=1e9+7;

// #define getchar getchar_unlocked
// #define putchar putchar_unlocked

template<class T>inline void read(T &s)
{
 s=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-'){f=-1;}c=getchar();}
 while(isdigit(c)){s=(s<<3)+(s<<1)+(c^48),c=getchar();}s*=f;return;
}
template<class T>inline void wr(T x)
{
 if(x<0){putchar('-'),x=-x;}int buf[21],top=0;while(x){buf[++top]=x%10,x/=10;}
 if(!top){buf[++top]=0;}while(top){putchar(buf[top--]^'0');}return;
}
template<class T,class ...A>inline void read(T &x,A &...a){read(x);read(a...);}

struct Matrix
{
 ll a[3][3];
 Matrix(){mem(a,0);}
 inline void init(){fo(i,0,2)a[i][i]=1;}
 Matrix operator*(const Matrix &b) const
 {
  Matrix c;
  fo(i,0,2)fo(k,0,2)fo(j,0,2)(c.a[i][j]+=a[i][k]*b.a[k][j])%=mod;
  return c;
 }
 ll* operator[](int i){return a[i];}
};
Matrix A,B,ans;
inline void solve()
{
 A[0][0]=2,A[0][1]=1,A[0][2]=1,A[1][0]=2,A[1][1]=1,A[1][2]=0,A[2][0]=1,A[2][1]=1,A[2][2]=1;
 B[0][0]=1,B[0][1]=0,B[0][2]=0,B[1][0]=2,B[1][1]=1,B[1][2]=0,B[2][0]=1,B[2][1]=1,B[2][2]=1;
 int n,m,lst=0,x;read(n,m);ans.init();
 fo(i,1,m)
 {
  read(x);int b=x-lst-1;Matrix C=A;
  for(;b;b>>=1,C=C*C)if(b&1)ans=C*ans;
  ans=B*ans,lst=x;
 }
 int b=n-lst-1;Matrix C=A;
 for(;b;b>>=1,C=C*C)if(b&1)ans=C*ans;
 ans=B*ans;
 wr(ans.a[2][0]%mod);
}
i32 main()
{
 auto begin=chrono::high_resolution_clock::now(); 
 // Mod=FastMod(mod);
 int T=1;//read(T);
 while(T--)solve();
 auto end=chrono::high_resolution_clock::now();
 auto elapsed=chrono::duration_cast<chrono::nanoseconds>(end-begin);
 // cerr<<"Time measured: "<<elapsed.count()*1e-9<<" seconds.\n";
 return 0;
}

Submission Info

Judge Result