#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define pii pair #define pLL pair #define mp make_pair #define mt make_tuple #define pq priority_queue #define pqg priority_queue,greater> #define pb push_back #define vecLL vector #define vecpii vector #define vecpLL vector #define vecbL vector #define mat vector #define endl "\n" #define REP(e,v) for(auto e:v) #define rep(i, a, n) for(LL i = a; i < n;i++) #define Arep(i, a, n) for(i = a; i < n;i++) #define MOD 1000000007 #define INF LLONG_MAX/2 #define DINF DBL_MAX/2 using namespace std; /*↓マイライブラリ↓*/ //clock_t start = clock(); // //clock_t end = clock(); // //const double time = static_cast(end - start) / CLOCKS_PER_SEC * 1000.0; //printf("time %lf[ms]\n", time); LL linp(){ LL x; scanf("%lld",&x); return x; } LL mod(LL i){ LL mi = i % MOD; if(mi < 0) mi += MOD; return mi; } mat mul(const mat &A,const mat &B){ mat C(A.size(),vecLL(B[0].size())); if(A[0].size() != B.size()){ cout << "エラー:掛け算不可" << endl; exit(0); } rep(i,0,A.size()){ rep(j,0,B[0].size()){ rep(k,0,B.size()){ C[i][j] = mod(C[i][j] + A[i][k]*B[k][j]); } } } return C; } mat matpow(const mat &A,LL n){ if(n == 1) return A; mat A_2 = matpow(A,n/2); A_2 = mul(A_2,A_2); if(n % 2 == 0){ return A_2; }else{ return mul(A,A_2); } } vecLL bit(LL i,LL N){ vecLL biti(N); rep(x,0,N){ biti[N - 1 - x] = (i >> x) & 1; } return biti; } void swap(LL &a, LL &b){ LL t = a; a = b; b = t; return ; } LL digit(LL x,LL n){ LL count = 1; while(x >= n){ x = x/n; count++; } return count; } LL gcd(LL i,LL j){ if(j != 0) return gcd(j, i % j); else return i; } pLL extgcd(LL a,LL m){//ax+my = 1の解 pLL ans; if(m != 0){ pLL next = extgcd(m,a%m); ans.first = next.second; ans.second = next.first-(a/m)*next.second; } else{ ans = pLL(1,0); } return ans; } LL div(LL a, LL b,LL m){ return mod(mod(a) * mod(extgcd(b,m).first)); } LL numperm(LL x,LL y){ LL res = 1; for(LL i = x; i >= y; i--){ res = mod(res * mod(i)); } return mod(res); } LL pow(LL x,LL y){ x = mod(x); if(y == 1){ return mod(x); } LL res = mod(pow(mod(x*x),y/2)); if(y % 2 == 0){ return res; } else{ return mod(x*res); } } bool isPrime(LL X){ rep(i,2,(LL)(sqrt(X)+1)){ if(X % i == 0){ return false; } } return true; } vecLL Eratosthenes(LL n){//素数のベクトルを返す bool isPrime[n]; fill(isPrime,isPrime+n,true); isPrime[0] = isPrime[1] = false; rep(i,2,sqrt(n)+1){ if(isPrime[i]){ for(LL j = 2*i ;j <= n ; j += i){ isPrime[j] = false; } } } vecLL P; rep(i,2,n+1){ if(isPrime[i]){ P.push_back(i); } } return P; } map factalization(LL N){ map fac; LL oriN = N; LL div = 1; for(LL i = 2;i*i <= N;++i){ while(N%i == 0){ fac[i]++; div *= i; N /= i; } } if(oriN/div != 1){ fac[oriN/div]++; } return fac; } struct edge {//枝 LL to,cost; double dcost;//コストが整数でない場合に使う } ; struct vertex{//頂点(枝付き) LL key; double dkey;//キーが整数でない場合に使う vector edges;//頂点から伸びる枝 }; class Graph{ public: LL V;//頂点数 vertex* vertices;//グラフ Graph(LL v){//頂点数を指定してグラフの初期化 V = v;//頂点数 vertices = new vertex[V];//頂点集合 rep(i,0,V){ vertices[i].key = -1;//キー初期値は-1 vertices[i].dkey = -1;//キー初期値は-1 } } void setDE(LL i,LL j,LL cos){//i→jにコストcosの有向枝を加える edge e; e.to= j; e.cost = cos; vertices[i].edges.push_back(e); return; } void setDE(LL i,LL j,double dcos){//i→jにコストcosの有向枝を加える edge e; e.to= j; e.dcost = dcos; vertices[i].edges.push_back(e); return; } void setUDE(LL i,LL j,LL cos){//(i,j)にコストcosの無向枝を加える edge ei,ej; ei.to = j; ej.to = i; ei.cost = ej.cost = cos; vertices[i].edges.push_back(ei); vertices[j].edges.push_back(ej); return; } void setUDE(LL i,LL j,double dcos){//(i,j)にコストcosの無向枝を加える edge ei,ej; ei.to = j; ej.to = i; ei.dcost = ej.dcost = dcos; vertices[i].edges.push_back(ei); vertices[j].edges.push_back(ej); return; } void setKey(LL i,LL newKey){//キー変更 vertices[i].key = newKey; } void setKey(LL i,double newKey){//キー変更 vertices[i].key = newKey; } edge getEdge(LL i,LL j){ rep(a,0,vertices[i].edges.size()){ if(vertices[i].edges[a].to == j){ return vertices[i].edges[a]; } } return (edge){j,INF,DINF};//なければ,コストINFの枝を返す } void bellman_ford(LL s,LL b[]){ fill(b,b+V,INF); b[s] = 0; while(true){ bool update = false; rep(i,0,V){ rep(j,0,vertices[i].edges.size()){ edge e = vertices[i].edges[j]; if(b[e.to] > b[i] + e.cost){ b[e.to] = b[i] + e.cost; update = true; } } } if(!update) break; } return; } void dijkstra(LL s, LL d[]) {//ダイクストラ(始点を入力とし、各点への最小距離を返す) priority_queue, greater > que; fill(d,d+V,INF); d[s] = 0; que.push(pLL(0, s)); while (!que.empty()) { pLL p = que.top(); que.pop(); LL v = p.second; if (d[v] < p.first) continue; rep(i,0, vertices[v].edges.size()) { edge e = vertices[v].edges[i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(pLL(d[e.to], e.to)); } } } return; } void warshall_floyd(LL **w){ rep(i,0,V){ rep(j,0,V){ w[i][j] = INF; } } rep(i,0,V){ rep(j,0,vertices[i].edges.size()){ w[i][vertices[i].edges[j].to] = vertices[i].edges[j].cost; } } rep(i,0,V){ w[i][i] = 0; } rep(i,0,V){ rep(j,0,V){ rep(k,0,V){ w[i][j] = min(w[i][j],w[i][k]+w[k][j]); } } } } }; class UF { public: LL N; LL* par; LL* rank; UF(LL n){ N = n; par = new LL[N]; rank = new LL[N]; rep(i,0,N){ par[i] = i; rank[i] = i; } return; } LL root(LL x){ if(x == par[x]) return x; else return par[x] = root(par[x]); } bool same(LL x,LL y){ return (root(x) == root(y)); } void Union(LL x,LL y){ LL rtx = root(x); LL rty = root(y); if(rank[rtx] < rank[rty]){ par[rtx] = rty; } else{ par[rty] = rtx; if(rank[rtx] == rank[rty]){ rank[rtx]++; } } } }; class ST{ }; /*↑マイライブラリ↑*/ LL solveA(){ string S; cin >> S; LL len = S.length(); rep(i,0,len-1){ if(S[i] == 'a' && S[i+1] == 'o'){ S[i] = 'k'; S[i+1] = 'i'; i++; } } cout << S; return 0; } LL solveB(){ LL N,K; cin >> N >> K; if(N >= K){ cout << K - 1; }else{ cout << -1; } return 0; } LL solveC(){ LL N,M,K,p,q; cin >> N >> M >> K >> p >> q; mat A(2,vecLL(2)); LL P = p*extgcd(q,MOD).first%MOD; A[0][0] = mod(1 - P);A[0][1] = mod(P); A[1][0] = mod(P) ;A[1][1] = mod(1 - P); mat A_k = matpow(A,K); LL tapin = 0; LL tapout = 0; rep(i,0,N){ LL x = linp(); if(i < M){ tapin = mod(tapin + x); }else{ tapout = mod(tapout + x); } } cout << mod(mod(tapin*A_k[0][0]) + mod(tapout*A_k[1][0])) << endl; return 0; } LL solveD(){ return 0; } LL solveE(){ return 0; } signed main(){ //solveA(); solveB(); //solveC(); //solveD(); //solveE(); return 0; }