stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define N 1000010

int i,n,y,L,cnt;

struct edge {

    int u, v, w;

}e[110];

inline void add(int u,int v,int w) {

    e[++cnt] = (edge) {u, v, w};

}

int main() {

    cin >> L;

    for (i = L; i; ++n, i >>= 1);

    for (i = 1; i < n; ++i)add(i, i + 1, 1 << i - 1), add(i, i + 1, 0);

    for (y = 1 << n - 1, i = 1; L != 1; ++i, L >>= 1)if (L & 1)add(i, n, y), y |= 1 << i - 1;

    printf("%d %d\n", n, cnt);

    for (i = 1; i <= cnt; ++i)printf("%d %d %d\n", e[i].u, e[i].v, e[i].w);

}


// Optimized solution to the same problem (faster):
#include <cstdio>



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

	for (int i = 1; i < cur; ++i)

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

	for (int i = 0; i < ct; ++i)

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



struct edge {

	int u, v, w;

	edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}

};



int main() {

	ios::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

	int l; cin >> l;

	int n = 32 - __builtin_clz(l);

	vector<edge> g;

	int u = 1;

	for (int i = 1; i < n; i++) {

		g.emplace_back(i, i + 1, u);

		g.emplace_back(i, i + 1, 0);

		u <<= 1;

	}

	for (int i = 0; i < n - 1; i++) {

		if (l >> i & 1) {

			g.emplace_back(i + 1, n, l >> (i + 1) << (i + 1));

		}

	}

	cout << n << ' ' << g.size() << endl;

	for (auto e : g) {

		cout << e.u << ' ' << e.v << ' ' << e.w << "\n";

	}

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

	for (int i = 1; i < cur; ++i)

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

	for (int i = 0; i < ct; ++i)

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



struct Data {

	int u, v, w;

	Data(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}

};



int main() {

	

	ios::sync_with_stdio(0);

	cin.tie(0), cout.tie(0);

	

	int L; cin >> L;

	int n = 32 - __builtin_clz(L);

	vector<Data> edges;

	

	for (int i = 1; i < n; i++) {

		edges.emplace_back(i, i + 1, 1 << i - 1);

		edges.emplace_back(i, i + 1, 0);

	}

	int cur = 1 << n - 1;

	for (int i = n - 2; i >= 0; i--) if (L >> i & 1) {

		edges.emplace_back(i + 1, n, cur);

		cur |= 1 << i;

	}

	

	cout << n << " " << edges.size() << "\n";

	for (auto it : edges) cout << it.u << " " << it.v << " " << it.w << "\n";

	

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



struct Edge {

	int u, v, w;

	Edge(int a = 0, int b = 0, int c = 0) {

		u = a, v = b, w = c;

	}

} edge[100];



int main() {

	int n, ct = 0;

	scanf("%d", &n);

--n;

	int cur = 20;

	while (n) {

		edge[ct++] = Edge(cur - 1, cur, (n + 2) / 2);

		edge[ct++] = Edge(cur - 1, cur, 1 - n % 2);

		if (n % 2 == 0)

			edge[ct++] = Edge(1, cur, 0);

		n = (n - 1) / 2;

		--cur;

	}

	for (int i = 1; i < cur; ++i)

		edge[ct++] = Edge(i, i + 1, 0);

	printf("20 %d\n", ct);

	for (int i = 0; i < ct; ++i)

		printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cfloat>

#include <map>

#include <utility>

#include <set>

#include <iostream>

#include <memory>

#include <string>

#include <vector>

#include <algorithm>

#include <functional>

#include <sstream>

#include <complex>

#include <stack>

#include <cstring>

#include <queue>

#include <sys/time.h>

using namespace std;

static const double EPS = 1e-10;

typedef long long ll;

#define rep(i,n) for(int i=0;i<(int)n;i++)

#define rev(i,n) for(int i=(int)n-1;i>=0;i--)

#define all(a) a.begin(),a.end()

#define mp(a,b) make_pair(a,b)

#define pb(a) push_back(a)

#define SS stringstream

#define bitcount(b) __builtin_popcount(b)

#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)



#define delete(a,n) a.erase(remove(all(a),n),a.end())

#define gcd(a,b) __gcd((a),(b))

#define lcm(a,b) ( (a)/__gcd((a),(b))*(b) )



template<typename T, typename S> vector<T>& operator<<(vector<T>& a, S b) { a.push_back(b); return a; }

template<typename T> void operator>>(vector<T>& a, int b) {while(b--)if(!a.empty())a.pop_back();}

bool isprime(int n){ if(n<2)return false;  for(int i=2;i*i<=n;i++)if(n%i==0)return false;  return true;} 

ll b_pow(ll x,ll n){return n ? b_pow(x*x,n/2)*(n%2?x:1) : 1ll;}

string itos(int n){stringstream ss;ss << n;return ss.str();}



int a[50000],b[50000],o[50000];

int main(){

	int H,W,q;

	while(cin >> H >> W >> q && H){

		int ans = 0;

		rep(i,q) cin >> a[i] >> b[i] >> o[i];

		set<int> g[2];

		rev(i,q){

			if(a[i]==0){

				if(!g[0].count(b[i]) && o[i]) ans += W - g[1].size();

				g[0].insert(b[i]);

			}else{

				if(!g[1].count(b[i]) && o[i]) ans += H - g[0].size();

				g[1].insert(b[i]);

			}

		}

		cout << ans << endl;

	}

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <tr1/unordered_set>

using namespace std;

int a[50000],b[50000],o[50000];

int main(){

	int H,W,q;

	while(scanf("%d%d%d",&H,&W,&q)&&H){

		int ans = 0;

		for(int i = 0 ; i < q ; i++)

			scanf("%d%d%d",&a[i],&b[i],&o[i]);

		tr1::unordered_set<int> g[2];

		for(int i = q-1 ; i >= 0 ; i--){

			if(a[i]==0){

				if(!g[a[i]].count(b[i]) && o[i]) ans += W - g[!a[i]].size();

				g[a[i]].insert(b[i]);

			}else{

				if(!g[1].count(b[i]) && o[i]) ans += H - g[0].size();

				g[1].insert(b[i]);

			}

		}

		printf("%d\n",ans);

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <algorithm>

#include <queue>

#define REP(i,n) for(int i=0; i<(int)(n); i++)



using namespace std;



int main(){

  int r, c, q;



  while(scanf("%d%d%d", &r, &c, &q), r + c + q){

    vector<int> a(q);

    vector<int> b(q);

    vector<int> o(q);



    vector<int> rs(r, -1);

    vector<int> cs(c, -1);



    REP(i,q) scanf("%d%d%d", &a[i], &b[i], &o[i]);



    reverse(a.begin(), a.end());

    reverse(b.begin(), b.end());

    reverse(o.begin(), o.end());



    int rr = 0;

    int cc = 0;

    int ans = 0;



    REP(i,q){

      if(a[i] == 0){

	if(rs[b[i]] == -1){

	  rs[b[i]] = o[i];

	  rr++;

	  if(o[i] == 1) ans += c - cc;

	}

      }else{

	if(cs[b[i]] == -1){

	  cs[b[i]] = o[i];

	  cc++;

	  if(o[i] == 1) ans += r - rr;

	}

      }

    }



    printf("%d\n", ans);

  }



  return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#define REP(i,n) for(int i=0; i<(int)(n); i++)



using namespace std;



int a[50000];

int b[50000];

int o[50000];



int rc[2][50000];



int main(){

  int rcs[2], q;



  while(scanf("%d%d%d", &rcs[0], &rcs[1], &q), rcs[0] + rcs[1] + q){

    REP(i,q) scanf("%d%d%d", &a[i], &b[i], &o[i]);



    int rrcc[2] = {0};

    int ans = 0;



    memset(rc[0], 0, sizeof(int) * rcs[0]);

    memset(rc[1], 0, sizeof(int) * rcs[1]);



    for(int i = q - 1; i >= 0; i--){

      if(!rc[a[i]][b[i]]){

	rc[a[i]][b[i]] = 1;

	rrcc[a[i]]++;

	if(o[i] == 1) ans += rcs[!a[i]] - rrcc[!a[i]];

      }

    }



    printf("%d\n", ans);

  }



  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;



int main(){

  int r,c,q,a[50000],b[50000],o[50000];

  int nr,nc;

  bool row[50000],col[50000];

  long long int ans;



  while(1){

    cin >> r >> c >> q;

    if(!r && !c && !q)break;



    for(int i=0;i<r;i++)row[i] = false;

    for(int i=0;i<c;i++)col[i] = false;



    ans = nr = nc = 0;

    for(int i=0;i<q;i++)cin >> a[i] >> b[i] >> o[i];



    for(int i=q-1;i>=0;i--){

      if(a[i]){

	if(!col[b[i]]){

	  if(o[i])ans += r-nr;

	  col[b[i]] = true;

	  nc++;

	}

      }else{

	if(!row[b[i]]){

	  if(o[i])ans += c-nc;

	  row[b[i]] = true;

	  nr++;

	}

      }

    }

    cout << ans << endl;

  }

}

// Optimized solution to the same problem (faster):
#include<cstdio>

using namespace std;



int main(){

  int r,c,q,a[50000],b[50000],o[50000];

  int nr,nc;

  bool row[50000],col[50000];

  long long int ans;



  while(1){

    scanf("%d %d %d",&r,&c,&q);

    if(!r && !c && !q)break;



    for(int i=0;i<r;i++)row[i] = false;

    for(int i=0;i<c;i++)col[i] = false;



    ans = nr = nc = 0;

    for(int i=0;i<q;i++)scanf("%d %d %d",&a[i],&b[i],&o[i]);



    for(int i=q-1;i>=0;i--){

      if(a[i]){

	if(!col[b[i]]){

	  if(o[i])ans += r-nr;

	  col[b[i]] = true;

	  nc++;

	}

      }else{

	if(!row[b[i]]){

	  if(o[i])ans += c-nc;

	  row[b[i]] = true;

	  nr++;

	}

      }

    }

 

    printf("%lld\n",ans);

  }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;



int main(){

  int r,c,q,a[50000],b[50000],o[50000];

  int nr,nc;

  bool row[50000],col[50000];

  int ans;



  while(1){

    cin >> r >> c >> q;

    if(!r && !c && !q)break;



    for(int i=0;i<r;i++)row[i] = false;

    for(int i=0;i<c;i++)col[i] = false;



    ans = nr = nc = 0;

    for(int i=0;i<q;i++)cin >> a[i] >> b[i] >> o[i];



    for(int i=q-1;i>=0;i--){

      if(a[i]){

	if(!col[b[i]]){

	  if(o[i])ans += r-nr;

	  col[b[i]] = true;

	  nc++;

	}

      }else{

	if(!row[b[i]]){

	  if(o[i])ans += c-nc;

	  row[b[i]] = true;

	  nr++;

	}

      }

    }

    cout << ans << endl;

  }

}

// Optimized solution to the same problem (faster):
#include<cstdio>

using namespace std;



int main(){

  int r,c,q,a[50000],b[50000],o[50000];

  int nr,nc;

  bool row[50000],col[50000];

  long long int ans;



  while(1){

    scanf("%d %d %d",&r,&c,&q);

    if(!r && !c && !q)break;



    for(int i=0;i<r;i++)row[i] = false;

    for(int i=0;i<c;i++)col[i] = false;



    ans = nr = nc = 0;

    for(int i=0;i<q;i++)scanf("%d %d %d",&a[i],&b[i],&o[i]);



    for(int i=q-1;i>=0;i--){

      if(a[i]){

	if(!col[b[i]]){

	  if(o[i])ans += r-nr;

	  col[b[i]] = true;

	  nc++;

	}

      }else{

	if(!row[b[i]]){

	  if(o[i])ans += c-nc;

	  row[b[i]] = true;

	  nr++;

	}

      }

    }

 

    printf("%lld\n",ans);

  }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ALL(x) begin(x), end(x)

#define VI vector<int>

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;



const int mod = 1e9+7;

int n;

char cand[4] = {'A', 'T', 'G', 'C'};

map<pair<int, string>, LL> M;

// ng: *AGC, *ACG, *GAC, A*GC, AG*C

bool ok(string last4) {

    if(last4[1]=='A' && last4[2]=='G' && last4[3]=='C') return false;

    if(last4[1]=='A' && last4[2]=='C' && last4[3]=='G') return false;

    if(last4[1]=='G' && last4[2]=='A' && last4[3]=='C') return false;

    if(last4[0]=='A' && last4[2]=='G' && last4[3]=='C') return false;

    if(last4[0]=='A' && last4[1]=='G' && last4[3]=='C') return false;

    return true;

}



LL dfs(int m, string last3) {

    if(m == n) return 1LL;

    if(M.count({m, last3})) return M[{m, last3}];



    LL res = 0;

    for(int i = 0; i < 4; i++) {

        string t = last3 + cand[i];

        if(!ok(t)) continue;

        (res += dfs(m+1, t.substr(1))) %= mod;

    }

    return M[{m, last3}] = res;

}



int main() {

    scanf("%d", &n);

    LL ans = dfs(0, "TTT");

    printf("%lld\n", ans % mod);

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef signed long long ll;



#undef _P

#define _P(...) (void)printf(__VA_ARGS__)

#define FOR(x,to) for(x=0;x<(to);x++)

#define FORR(x,arr) for(auto& x:arr)

#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)

#define ALL(a) (a.begin()),(a.end())

#define ZERO(a) memset(a,0,sizeof(a))

#define MINUS(a) memset(a,0xff,sizeof(a))

//-------------------------------------------------------



int N;

ll dp[101][5][5][5];

ll mo=1000000007;



void solve() {

    int i,j,k,l,r,x,y,z; string s;

    

    cin>>N;

    dp[0][3][3][3]=1;

    

    FOR(i,N) {

        FOR(x,4) FOR(y,4) FOR(z,4) FOR(j,4) {

            if(y==0 && z==1 && j==2) continue;

            if(y==0 && z==2 && j==1) continue;

            if(y==1 && z==0 && j==2) continue;

            if(x==0 && y==1 && j==2) continue;

            if(x==0 && z==1 && j==2) continue;

            (dp[i+1][y][z][j]+=dp[i][x][y][z])%=mo;

        }

    }

    

    ll ret=0;

    FOR(x,4) FOR(y,4) FOR(z,4) ret+=dp[N][x][y][z];

    cout<<ret%mo<<endl;

}





int main(int argc,char** argv){

    string s;int i;

    if(argc==1) ios::sync_with_stdio(false), cin.tie(0);

    FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);

    cout.tie(0); solve(); return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

long long dp[101][5][5][5] = {};



void solve() {

    dp[0][0][0][0] = 1;

    for(int n=1; n<=100; ++n) {

        for(int i=0; i<5; ++i) {

            for(int j=0; j<5; ++j) {

                for(int k=0; k<5; ++k) {

                    for(int l=1; l<5; ++l) {

                        if(j == 1 && k == 2 && l == 3) continue;

                        if(i == 1 && k == 2 && l == 3) continue;

                        if(j == 2 && k == 1 && l == 3) continue;

                        if(j == 1 && k == 3 && l == 2) continue;

                        if(i == 1 && j == 2 && l == 3) continue;

                        dp[n][j][k][l] = (dp[n][j][k][l] + dp[n-1][i][j][k]) % MOD;

                    }

                }

            }

        }

    }

}



int main() {

    solve();

    int N;

    cin >> N;

    long long res = 0;

    for(int i=1; i<5; ++i) {

        for(int j=1; j<5; ++j) {

            for(int k=1; k<5; ++k) {

                res = (res + dp[N][i][j][k]) % MOD;

            }

        }

    }

    cout << res << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

using namespace std;



int res[101] = {

0,

0,

0,

61,

230,

865,

3247,

12185,

45719,

171531,

643550,

2414454,

9058467,

33985227,

127504505,

478366600,

794717734,

733354121,

261943303,

776803305,

580025381,

51688048,

44657419,

737209731,

604119499,

159693437,

858533109,

639056669,

549054109,

996291083,

531294469,

23314687,

783022045,

855462856,

649970414,

68697295,

409213624,

604356692,

88638656,

978442997,

534833116,

763737161,

785892908,

123883652,

639213333,

181836645,

998121103,

124885216,

501575626,

39816123,

113468411,

799008836,

775465589,

256852905,

664630886,

971550783,

751629411,

51018086,

702530485,

725438992,

696683714,

792638194,

221791721,

149602322,

414054379,

986519078,

981760191,

305799096,

515140586,

406959393,

975058685,

245601370,

324759692,

673385295,

191483611,

570246669,

427196161,

781042769,

569725155,

842176273,

25328739,

847501730,

206282374,

353770801,

323137024,

371653459,

940737264,

123820509,

915711339,

847205021,

252858375,

718889563,

866398347,

738390145,

133009077,

333099663,

170591295,

329869205,

616680192,

597534442,

388130742

};



int main() {

    int N; cin >> N;

    cout << res[N] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define per(i,a,b) for(int i=(a);i>=(b);i--)

#define REP(i,n) for(int i=(0);i<(n);i++)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

typedef vector<int> vi;

typedef long long ll;



template<class T> inline void read(T &x){

	int f=0;x=0;char ch=getchar();

	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');

	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';

	if(f)x=-x;

}



const int mod=1e9+7,N=3005;

const ll inv2=(mod+1)/2;

int f[N][N],g[N],h[N],a[N],n,Q,x,y,pw=1,ans;



void add(int &x,int y){

	x=(x+y>=mod?x+y-mod:x+y);

}



int main(){

	read(n),read(Q);

	rep(i,1,n)read(a[i]);

	rep(i,1,n)rep(j,1,n)

		f[i][j]=(a[i]>a[j]);

	rep(k,1,Q){

		read(x),read(y),pw=pw*2%mod;

		rep(i,1,n)if(i!=x&&i!=y){

			g[i]=inv2*(f[x][i]+f[y][i])%mod;

			h[i]=inv2*(f[i][x]+f[i][y])%mod;

		}

		rep(i,1,n)if(i!=x&&i!=y){

			f[x][i]=f[y][i]=g[i];

			f[i][x]=f[i][y]=h[i];

		}

		f[x][y]=f[y][x]=inv2*(f[x][y]+f[y][x])%mod;

	}

	rep(i,1,n)rep(j,i+1,n)

		add(ans,f[i][j]);

	ans=(ll)ans*pw%mod;

	cout<<ans<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



const int _ = 3e3 + 5, p = 1e9 + 7;



int n, m, a[_], dp[_][_];



inline int power(int x, int k) {

    int res = 1;

    for (; k; k >>= 1, x = 1ll * x * x % p)

        if (k & 1) res = 1ll * res * x % p;

    return res % p;

}



int main() {

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) scanf("%d", a + i);

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j <= n; ++j) dp[i][j] = a[i] < a[j];

    int inv2 = power(2, p - 2);

    for (int x, y, i = 1; i <= m; ++i) {

        scanf("%d %d", &x, &y);

        dp[x][y] = dp[y][x] = 1ll * inv2 * ((dp[x][y] + dp[y][x]) % p) % p;

        for (int j = 1; j <= n; ++j) {

            if (j == x | j == y) continue ;

            dp[x][j] = dp[y][j] = 1ll * inv2 * ((dp[x][j] + dp[y][j]) % p) % p;

            dp[j][x] = dp[j][y] = 1ll * inv2 * ((dp[j][x] + dp[j][y]) % p) % p;

        }

    }

    int ans = 0;

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j < i; ++j) ans = (ans + dp[i][j]) % p;

    ans = 1ll * ans * power(2, m) % p;

    printf("%d\n", ans);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define maxn 3010

const int p=1e9+7;

const int inv2=500000004;

template <typename T>inline T read()

{

    register T sum=0;

    register char cc=getchar();

    int sym=1;

    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();

    if(cc=='-')sym=-1,cc=getchar();

    sum=sum*10+cc-'0';

    cc=getchar();

    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();

    return sym*sum;

}

template <typename T>inline T read(T &a)

{

    a=read<T>();

    return a;

}

template <typename T,typename... Others> inline void read(T& a, Others&... b)

{

    a=read(a);

	read(b...);

}

int n,Q,ans,pw=1,a[maxn],p1[maxn],p2[maxn],f[maxn][maxn];

int add(int x,int y)

{

	x+=y;

	return x>=p? x-p:x;

}

void Add(int &x,int y)

{

	x+=y;

	if(x>=p)

		x-=p;

}

int mul(int x,int y)

{

	return 1ll*x*y%p;

}

int main()

{

	read(n,Q);

	for(int i=1;i<=n;i++)

		read(a[i]);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			f[i][j]=a[i]>a[j];

	for(int i=1;i<=Q;i++)

		read(p1[i],p2[i]);

	for(int i=1;i<=Q;i++)

	{

		static int g[maxn][maxn];

		for(int x=1;x<=n;x++)

			if(x!=p1[i]&&x!=p2[i])

			{

				g[x][p1[i]]=mul(inv2,add(f[x][p1[i]],f[x][p2[i]]));

				g[p1[i]][x]=mul(inv2,add(f[p1[i]][x],f[p2[i]][x]));

				g[x][p2[i]]=mul(inv2,add(f[x][p2[i]],f[x][p1[i]]));

				g[p2[i]][x]=mul(inv2,add(f[p2[i]][x],f[p1[i]][x]));

			}

		for(int x=1;x<=n;x++)

			if(x!=p1[i]&&x!=p2[i])

			{

				f[x][p1[i]]=g[x][p1[i]];

				f[p1[i]][x]=g[p1[i]][x];

				f[x][p2[i]]=g[x][p2[i]];

				f[p2[i]][x]=g[p2[i]][x];

			}

		f[p1[i]][p2[i]]=f[p2[i]][p1[i]]=mul(inv2,add(f[p1[i]][p2[i]],f[p2[i]][p1[i]]));

		pw=add(pw,pw);

	}

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++)

			Add(ans,f[i][j]);

	printf("%d\n",mul(ans,pw));

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



const int _ = 3e3 + 5, p = 1e9 + 7;



int n, m, a[_], dp[_][_];



inline int power(int x, int k) {

    int res = 1;

    for (; k; k >>= 1, x = 1ll * x * x % p)

        if (k & 1) res = 1ll * res * x % p;

    return res % p;

}



int main() {

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) scanf("%d", a + i);

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j <= n; ++j) dp[i][j] = a[i] < a[j];

    int inv2 = power(2, p - 2);

    for (int x, y, i = 1; i <= m; ++i) {

        scanf("%d %d", &x, &y);

        dp[x][y] = dp[y][x] = 1ll * inv2 * ((dp[x][y] + dp[y][x]) % p) % p;

        for (int j = 1; j <= n; ++j) {

            if (j == x | j == y) continue ;

            dp[x][j] = dp[y][j] = 1ll * inv2 * ((dp[x][j] + dp[y][j]) % p) % p;

            dp[j][x] = dp[j][y] = 1ll * inv2 * ((dp[j][x] + dp[j][y]) % p) % p;

        }

    }

    int ans = 0;

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j < i; ++j) ans = (ans + dp[i][j]) % p;

    ans = 1ll * ans * power(2, m) % p;

    printf("%d\n", ans);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream> 

#include <cstdio> 

#include <cstdlib> 

#include <cstring> 

#include <cmath> 

#include <algorithm>  

using namespace std; 

const int MAX_N = 3e3 + 5; 

const int Mod = 1e9 + 7; 

int fpow(int x, int y) {

	int res = 1; 

	while (y) { 

		if (y & 1) res = 1ll * res * x % Mod; 

		x = 1ll * x * x % Mod; 

		y >>= 1; 

	} 

	return res; 

} 

const int inv = fpow(2, Mod - 2); 

int N, Q, a[MAX_N]; 

int f[MAX_N][MAX_N]; 

int main () { 

	scanf("%d %d", &N, &Q); 

	for (int i = 1; i <= N; i++) scanf("%d", a + i); 

	for (int i = 1; i <= N; i++) 

		for (int j = 1; j <= N; j++) f[i][j] = a[i] < a[j]; 

	for (int i = 1; i <= Q; i++) { 

		int x, y; scanf("%d %d", &x, &y); 

		f[x][y] = f[y][x] = 1ll * (f[x][y] + f[y][x]) * inv % Mod; 

		for (int j = 1; j <= N; j++) { 

			if (j == x || j == y) continue; 

			f[x][j] = f[y][j] = 1ll * (f[x][j] + f[y][j]) * inv % Mod; 

			f[j][x] = f[j][y] = 1ll * (f[j][x] + f[j][y]) * inv % Mod; 

		} 

	} 

	int ans = 0; 

	for (int i = 1; i <= N; i++) 

		for (int j = 1; j < i; j++) 

			ans = (ans + f[i][j]) % Mod; 

	printf("%lld\n", 1ll * ans * fpow(2, Q) % Mod); 

    return 0;  

} 

// Optimized solution to the same problem (faster):
#include <cstdio>



const int _ = 3e3 + 5, p = 1e9 + 7;



int n, m, a[_], dp[_][_];



inline int power(int x, int k) {

    int res = 1;

    for (; k; k >>= 1, x = 1ll * x * x % p)

        if (k & 1) res = 1ll * res * x % p;

    return res % p;

}



int main() {

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) scanf("%d", a + i);

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j <= n; ++j) dp[i][j] = a[i] < a[j];

    int inv2 = power(2, p - 2);

    for (int x, y, i = 1; i <= m; ++i) {

        scanf("%d %d", &x, &y);

        dp[x][y] = dp[y][x] = 1ll * inv2 * ((dp[x][y] + dp[y][x]) % p) % p;

        for (int j = 1; j <= n; ++j) {

            if (j == x | j == y) continue ;

            dp[x][j] = dp[y][j] = 1ll * inv2 * ((dp[x][j] + dp[y][j]) % p) % p;

            dp[j][x] = dp[j][y] = 1ll * inv2 * ((dp[j][x] + dp[j][y]) % p) % p;

        }

    }

    int ans = 0;

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j < i; ++j) ans = (ans + dp[i][j]) % p;

    ans = 1ll * ans * power(2, m) % p;

    printf("%d\n", ans);

    return 0;

}


// Fastest known solution for this problem: