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

#include<algorithm>

#include<vector>

#include<string>

#include<cmath>

#include<cstdio>

#include<queue>

#include<deque>

#include<map>

#include<stack>

#include<set>

#include<utility>

using namespace std;

typedef pair<int,int> ii;

typedef long long ll;

typedef pair<ll,ll> p;

typedef unsigned long long int ull;

int dy[]={1,0,-1,0};

int dx[]={0,1,0,-1};

const int MAXN=100000;

const int MAXE=100000;

const int MAXV=10000;

const ll INF=2e18;

ll MOD=1e9+7;



ll power(ll a,ll x){

    ll res=1;

  while(x>0){

    if(x&1) res=res*a%13;

    a=a*a%13;

    x>>=1;

  }

    return res;

}



int main(){

    string s;cin>>s;

    int n=(int)s.size();

    vector<vector<ll> > dp(n+1,vector<ll>(13,0));

    dp[n][0]=1;

    for(int i=n;i>0;i--){

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

            if(s[i-1]=='?'){

                for(int d=0;d<10;d++){

                    dp[i-1][(d*power(10,n-i)+j)%13]+=dp[i][j];

                    dp[i-1][(d*power(10,n-i)+j)%13]%=MOD;

                }

            }else{

                int d=(int)(s[i-1]-'0');

                dp[i-1][(d*power(10,n-i)+j)%13]+=dp[i][j];

                dp[i-1][(d*power(10,n-i)+j)%13]%=MOD;

            }

        }

    }

    cout<<dp[0][5]<<endl;

    return 0;

}

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

#include<algorithm>

#include<vector>

#include<string>

#include<cmath>

#include<cstdio>

#include<queue>

#include<deque>

#include<map>

#include<stack>

#include<set>

#include<utility>

using namespace std;

typedef pair<int,int> ii;

typedef long long ll;

typedef pair<ll,ll> p;

typedef unsigned long long int ull;

int dy[]={1,0,-1,0};

int dx[]={0,1,0,-1};

const int MAXN=100000;

const int MAXE=100000;

const int MAXV=10000;

const ll INF=2e18;

ll MOD=1e9+7;



ll power(ll a,ll x){

    ll res=1;

    while(x>0){

        if(x&1) res=res*a%13;

        a=a*a%13;

        x>>=1;

    }

    return res;

}



int main(){

    string s;cin>>s;

    int n=(int)s.size();

    vector<vector<ll> > dp(n+1,vector<ll>(13,0));

    dp[0][0]=1;

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

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

            if(s[i]=='?'){

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

                    dp[i+1][(j*10+k)%13]+=dp[i][j];

                    dp[i+1][(j*10+k)%13]%=MOD;

                }

            }else{

                int k=(int)(s[i]-'0');

                dp[i+1][(j*10+k)%13]+=dp[i][j];

                dp[i+1][(j*10+k)%13]%=MOD;

            }

        }

    }

    cout<<dp[n][5]<<endl;

    return 0;

}

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

#define ft first

#define sc second

#define pt(sth) cout << sth << "\n"

#define chmax(a, b) {if(a<b) a=b;}

#define chmin(a, b) {if(a>b) a=b;}

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

static const ll INF=1e18;

static const ll MAX=1e5+7;

static ll MOD=1e9+7;

ll max(ll a, ll b) {return a>b?a:b;}

ll min(ll a, ll b) {return a<b?a:b;}





ll ten(ll n) {

  ll res=1;

  ll x=10;

  while(n>0) {

    if(n&1) res=res*x%13;

    x=x*x%13;

    n>>=1;

  }

  return res;

}



ll dp[MAX][13]={};

int main(void) {

  string s;

  cin >> s;

  ll i, j, k;

  ll N=s.size();

  

  dp[0][0]=1;

  for(i=0; i<N; i++) {

    for(j=0; j<13; j++) {

      if(s[i]=='?') {

        for(k=0; k<10; k++) {

          moC(dp[i+1][(j+k*ten(N-i-1))%13], +, dp[i][j]);

        }

      }else {

        moC(dp[i+1][(j+(s[i]-'0')*ten(N-i-1))%13], +, dp[i][j]);

      }

    }

  }

  

  pt(dp[N][5]);

}


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

#define pt(sth) cout << sth << "\n"

#define chmax(a, b) {if(a<b) a=b;}

#define chmin(a, b) {if(a>b) a=b;}

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

static const ll INF=1e18;

static const ll MAX=101010;

static const ll MOD=1e9+7;

static const ll LOGN=55;





ll dp[MAX][15]={};



int main(void) {

  string s;

  cin >> s;

  ll N=(ll)s.size();

  ll i, j, k;

  

  dp[0][0]=1;

  for(i=0; i<N; i++) {

    for(j=0; j<13; j++) {

      

      if(s[i]=='?')

        for(k=0; k<10; k++)

          moC(dp[i+1][(j*10+k)%13], +, dp[i][j]);

      else

        moC(dp[i+1][(j*10+s[i]-'0')%13], +, dp[i][j]);

      

    }

  }

  

  pt(dp[N][5]);

  

  

}










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



using namespace std;

const int N = 1e5 + 3, MOD = 1e9 + 7;

char s[N];

int mem[N][13];

int go(int i, int m) {

	if (!s[i])

		return m == 5;

	int &ret = mem[i][m];

	if (~ret)

		return ret;

	ret = 0;

	if (s[i] == '?')

		for (int d = 0; d <= 9; ++d)

			ret = (ret + go(i + 1, (m * 10 + d) % 13)) % MOD;

	else

		ret = go(i + 1, (m * 10 + s[i] - '0') % 13);

	return ret;

}

int main() {

#ifndef ONLINE_JUDGE

//	freopen("input.in", "r", stdin);

//	freopen("output.out", "w", stdout);

#endif

	scanf("%s", s);

	memset(mem, -1, sizeof mem);

	printf("%d\n", go(0, 0));

	return 0;

}

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

using namespace std;



const int mxn = 1e5 + 5;

const long long mod = 1e9 + 7;



long long dp[mxn][15];



int main() {

    string s;

    cin >> s;

    dp[int(s.size())][0] = 1;

    for (int i = int(s.size()) - 1, ex = 1; i >= 0; i--) {

        if (s[i] == '?') {

            for (int c = 0; c < 10; c++) {

                for (int t = 0; t < 13; t++) {

                    dp[i][(c * ex + t) % 13] += dp[i + 1][t];

                    dp[i][(c * ex + t) % 13] %= mod;

                }

            }

        } else {

            int c = s[i] - '0';

            for (int t = 0; t < 13; t++) {

                dp[i][(c * ex + t) % 13] = dp[i + 1][t];

            }

        }

        ex = (ex * 10) % 13;

    }

    cout << dp[0][5] << endl;

}




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



using namespace std;



const int N = 1e5 + 5 , MOD = 1e9 + 7;

int p[N] , memo[N][14];

string s;



int mul(int a , int b , int m) {

    return a * 1ll * b % m;

}



int add(int a , int b , int m) {

    a += b;

    while (a >= m) a -= m;

    while (a < 0) a += m;

    return a;

}



int solve (int i , int m) {

    if (i == s.size())

        return m == 5;



    int &ret = memo[i][m];

    if (~ret)

        return ret;



    if (s[i] != '?')

        return ret = solve(i + 1 , add(m , mul(s[i] , p[s.size() - i - 1] , 13) , 13));



    ret = 0;



    for (int j = 0 ;j <= 9 ;j++)

        ret = add(ret , solve(i + 1 , add(m , mul(j , p[s.size() - i - 1] , 13) , 13)) , MOD);



    return ret;

}



int main() {

    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);



    p[0] = 1;

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

        p[i] = p[i - 1] * 10 % 13;



    cin >> s;

    for (char &c : s) if (c != '?') c -= '0';

    memset(memo , -1 , sizeof memo);

    cout << solve(0 , 0);

}

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

using namespace std;



const int mxn = 1e5 + 5;

const long long mod = 1e9 + 7;



long long dp[mxn][15];



int main() {

    string s;

    cin >> s;

    dp[int(s.size())][0] = 1;

    for (int i = int(s.size()) - 1, ex = 1; i >= 0; i--) {

        if (s[i] == '?') {

            for (int c = 0; c < 10; c++) {

                for (int t = 0; t < 13; t++) {

                    dp[i][(c * ex + t) % 13] += dp[i + 1][t];

                    dp[i][(c * ex + t) % 13] %= mod;

                }

            }

        } else {

            int c = s[i] - '0';

            for (int t = 0; t < 13; t++) {

                dp[i][(c * ex + t) % 13] = dp[i + 1][t];

            }

        }

        ex = (ex * 10) % 13;

    }

    cout << dp[0][5] << endl;

}




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

#include <cstring>

# define mod 1000000007

using namespace std;

typedef long long ll;

ll dp[100009][13];

int main(){

	string s;

	cin>>s;

	memset(dp,0,sizeof(dp));

	if(s[0]=='?')

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

			dp[0][i]=1;

	else

		dp[0][s[0]-'0']=1;

		int len=s.length();

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

	{

		if(s[i]=='?')

		{

			for(int j=0;j<13;j++)

				for(int k=0;k<10;k++)

				{

					dp[i][(j*10+k)%13]+=dp[i-1][j];

					dp[i][(j*10+k)%13]%=mod;

				}

		}

		else

		{

			for(int j=0;j<13;j++)

			{

				dp[i][(s[i]-'0'+j*10)%13]+=dp[i-1][j];

				dp[i][(s[i]-'0'+j*10)%13]%=mod;

			}

		}

	}

		 cout<<dp[len-1][5]<<endl;

	return 0;

} 

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

#include <cstring>

#include <algorithm>

using namespace std;

const int maxd = 1e5+10;

const int mod = 1e9+7;

char s[maxd];

int dp[maxd][20];

int main()

{

	// freopen("a.in","r",stdin);

	// freopen("k.out","w",stdout);

	scanf("%s",s+1);

	dp[0][0] = 1;

	for(int i=1;s[i];i++)

	{

		if(s[i] != '?')

		{

			int k = s[i] - '0';

			for(int j=0;j<13;j++)

				dp[i][(j*10+k)%13] = (1ll * dp[i][(j*10+k)%13] + dp[i-1][j])%mod;

		}

		else 

		{

			for(int k=0;k<10;k++)

				for(int j=0;j<13;j++)

					dp[i][(j*10+k)%13] = (1ll * dp[i][(k+j*10)%13] + dp[i-1][j])%mod;

		}

	}

	printf("%d",dp[strlen(s+1)][5]);

	return 0;

}

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

#define maxn 100005

using namespace std;

typedef long long ll;

char str[maxn];

ll dp[maxn][20];

const int mod=1e9+7;

int main()

{

    scanf("%s",str+1);

    int len=strlen(str+1);

    dp[0][0]=1;

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

        if(str[i]!='?'){

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

                dp[i][(j*10+str[i]-'0')%13]=(dp[i][(j*10+str[i]-'0')%13]+dp[i-1][j])%mod;

            }

        }

        else{

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

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

                    dp[i][(k*10+j)%13]=(dp[i][(k*10+j)%13]+dp[i-1][k])%mod;

                }

            }

        }

    }

    printf("%lld\n",dp[len][5]);

    return 0;

}

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

#include <cstring>

#include <algorithm>

using namespace std;

const int maxd = 1e5+10;

const int mod = 1e9+7;

char s[maxd];

int dp[maxd][20];

int main()

{

	// freopen("a.in","r",stdin);

	// freopen("k.out","w",stdout);

	scanf("%s",s+1);

	dp[0][0] = 1;

	for(int i=1;s[i];i++)

	{

		if(s[i] != '?')

		{

			int k = s[i] - '0';

			for(int j=0;j<13;j++)

				dp[i][(j*10+k)%13] = (1ll * dp[i][(j*10+k)%13] + dp[i-1][j])%mod;

		}

		else 

		{

			for(int k=0;k<10;k++)

				for(int j=0;j<13;j++)

					dp[i][(j*10+k)%13] = (1ll * dp[i][(k+j*10)%13] + dp[i-1][j])%mod;

		}

	}

	printf("%d",dp[strlen(s+1)][5]);

	return 0;

}

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

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using namespace std;

#define Khela ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long int

#define llu long long unsigned int

#define pf printf

#define sf scanf

#define f first

#define s second

#define pb push_back

#define mk make_pair

#define pii pair<int ,int>

#define PII pair<ll ,ll>

 

int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};

int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};

int dx4[] = {0, 0, 1, -1};

int dy4[] = {1, -1, 0, 0};

 

typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

int Set(int N,int pos){return N=N | (1<<pos);}

int reset(int N,int pos){return N= N & ~(1<<pos);}

bool check(int N,int pos){return (bool)(N & (1<<pos));}

const int max=1e9+100;

const ll  MAX=1e18+500;

const int sz=1e5+100;

const ll mod=1e9+7;

int mark[sz];

ll dp[sz][14];

ll n;

string str;

ll cholo(ll id,ll sum)

{

    if(id>=n){

        if(sum%13==5) return 1;

        else return 0;

    }



    ll &ret=dp[id][sum];

    if(~ret) return ret;

    ll tot=0;

    if(str[id] != '?') ret=cholo(id+1,(sum*10+(str[id]-'0'))%13);

    else{

        for(ll i=0;i<=9;i++) tot=(tot+cholo(id+1,(sum*10+i)%13))%mod;

        ret=tot;

    }



    return ret;

    

    

}

int main()

{

    Khela

    ll a,b,c,i,j,k,q,p,x,y,ct,ct1,m,l,r,x1,y1,mn,h,sum1,in,z,mid,mx;

    char ch;

    double d;

    //string str1;

    bool bl,bl1;

    int t,cs=1;

    while(cin>>str)

    {

        memset(dp,-1,sizeof dp);

        n=str.length();

        ll ans=cholo(0,0);

        cout<<ans<<endl;

      

        

    }











}

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

using namespace std;

const int mod = 1e9 + 7;

char s[100005];

int dp[100005][13]; //dp[i][j]表示到第i个字符为止，除以13余j(j表示的是到i-1为止模13余j)有多少种情况

// 难在找出状态转移方程

int main()

{

   // cout<<mod<<'\n';

    

    scanf("%s", s + 1);

    int n = strlen(s + 1);

    dp[0][0] = 1;

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

    {

        if (s[i] != '?')

        {

            s[i] -= '0';

            for (int j = 0; j < 13; j++)

            {

                dp[i][(j * 10 + s[i]) % 13] = (dp[i][(j * 10 + s[i]) % 13] + dp[i - 1][j]) % mod;

            }

        }

        else

        {

            for (int k = 0; k < 10; k++)

            {

                for (int j = 0; j < 13; j++)

                {

                    dp[i][(j * 10 + k) % 13] = (dp[i][(j * 10 + k) % 13] + dp[i - 1][j]) % mod;

                }

            }

        }

    }

    printf("%d\n", dp[n][5]);

}

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

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

#define rep(i, s, N) for(ll i{s}; i < N; i++)

using namespace std;using ll = long long int;const int MOD = (int)1e9+7;template<class T>vector<T> mvec(size_t a){return vector<T>(a);}template<class T, class... Ts>auto mvec(size_t a, Ts... ts){return vector<decltype(mvec<T>(ts...))>(a, mvec<T>(ts...));}



int main(){

  string S;

  cin >> S;

  ll N = S.size(); reverse(all(S));

  auto DP = mvec<ll>(N+1,13); DP[0][0] = 1;

  auto d13 = [](ll n) -> ll{

    return (13 + n % 13)%13;

  };

  auto deal = [&](ll i, ll j, ll l) -> void{

    ll k{};

    k = l + d13(j*pow(10, i%3)) * pow(-1, i/3);

    DP[i+1][d13(k)] += DP[i][l]%MOD;

  };

  rep(i, 0, N) rep(l, 0, 13){

    if(S[i] == '?') rep(j, 0, 10) deal(i, j, l);

    else deal (i, S[i] - '0', l);

  }

  cout << DP[N][5]%MOD << "\n";

}

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

#define rep(i,j) for(int i{};i<j;i++)

using namespace std;int d[100001][13];void f(int i, int j, int k){(d[i+1][k%13]+=d[i][j])%=1000000007;}main(){string s;cin>>s;d[0][0]=1;rep(i,s.size())rep(j,13){if(s[i]=='?')rep(k,10)f(i,j,j*10+k);else f(i,j,j*10+s[i]-'0');}cout<<d[s.size()][5];}

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

#define rep(i, N) for(int i{};i<N;i++)

using namespace std;

int M = 1e9+7;

int p[100001][13];

string S;

int d(int n){

  return (13 + n%13)%13;

}

void f(int i, int j, int l){

  int k{};

  k = l + d(j*pow(10, i%3)) * pow(-1, i/3);

  (p[i+1][d(k)] += p[i][l]) %= M;

}

int main(){

  cin >> S;

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

  p[0][0] = 1;

  rep(i, S.size()) rep(l, 13){

    if(S[i] == '?') rep(j, 10) f(i, j, l);

    else f(i, S[i] - '0', l);

  }

  cout<<p[S.size()][5]<<"\n";

}

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

#define rep(i,j) for(int i{};i<j;i++)

using namespace std;int d[100001][13];void f(int i, int j, int k){(d[i+1][k%13]+=d[i][j])%=1000000007;}main(){string s;cin>>s;d[0][0]=1;rep(i,s.size())rep(j,13){if(s[i]=='?')rep(k,10)f(i,j,j*10+k);else f(i,j,j*10+s[i]-'0');}cout<<d[s.size()][5];}

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

#define rep(i, N) for(int i{};i<N;i++)

using namespace std;

int M = 1e9+7;

int p[100001][13];

string S;

int d(int n){

  return (13 + n%13)%13;

}

void f(int &i, int j, int &l){

  int k{};

  k = l + d(j*pow(10, i%3)) * pow(-1, i/3);

  (p[i+1][d(k)] += p[i][l]) %= M;

}

int main(){

  cin >> S;

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

  p[0][0] = 1;

  rep(i, S.size()) rep(l, 13){

    if(S[i] == '?') rep(j, 10) f(i, j, l);

    else f(i, S[i] - '0', l);

  }

  cout<<p[S.size()][5]<<"\n";

}


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

#define rep(i, N) for(int i{};i<N;i++)

using namespace std;

int M = 1e9+7;

int p[100001][13];

string S;

int d(int n){

  return (13 + n%13)%13;

}

void f(int &i, int j, int &l){

  int k{};

  k = l + d(j*(i%3==0?1:i%3==1?10:100)) * (1-i/3%2*2);

  (p[i+1][d(k)] += p[i][l]) %= M;

}

int main(){

  cin >> S;

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

  p[0][0] = 1;

  rep(i, S.size()) rep(l, 13){

    if(S[i] == '?') rep(j, 10) f(i, j, l);

    else f(i, S[i] - '0', l);

  }

  cout<<p[S.size()][5]<<"\n";

}


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

#include <vector>

#include <algorithm>

using namespace std;



int main(){

	int h, n, p, m, k;

	scanf("%d%d%d%d%d", &h, &n, &p, &m, &k);

	vector<int> v(h, -1);

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

		int a, b;

		scanf("%d%d", &a, &b);

		v[a - 1] = b - 1;

	}



	double cmb[512][512] = {};

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

		cmb[i][0] = 1;

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

			cmb[i][j] = cmb[i - 1][j - 1] + cmb[i - 1][j];

		}

	}



	int rst = h - m;

	vector<vector<double> > dp1(k + 1, vector<double>(n)), dp2;

	dp2 = dp1;

	dp1[k][p - 1] = 1;

	for(int g = h - 1; g >= 0; --g){

		if(v[g] == -1){

			dp2[0] = dp1[0];

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

				double pr1 = 1 - cmb[rst - 1][i] / cmb[rst][i];

				double pr2 = pr1 / (n - 1);

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

					dp2[i][j] = dp1[i][j] * (1 - pr1);

				}

				dp2[i - 1][0] += (dp1[i][0] * (n - 2) + dp1[i][1]) * pr2;

				dp2[i - 1][n - 1] += (dp1[i][n - 1] * (n - 2) + dp1[i][n - 2]) * pr2;

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

					dp2[i - 1][j] += (dp1[i][j] * (n - 3) + dp1[i][j - 1] + dp1[i][j + 1]) * pr2;

				}

			}

			dp1.swap(dp2);

			--rst;

		}

		else{

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

				swap(dp1[i][v[g]], dp1[i][v[g] + 1]);

			}

		}

	}

	double ans = *max_element(dp1[0].begin(), dp1[0].end());

	printf("%.9f\n", ans);

}

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

#include <vector>

#include <algorithm>

using namespace std;



int main(){

	int h, n, p, m, k;

	scanf("%d%d%d%d%d", &h, &n, &p, &m, &k);

	vector<int> v(h, -1);

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

		int a, b;

		scanf("%d%d", &a, &b);

		v[a - 1] = b - 1;

	}



	int rst = h - m;

	vector<vector<double> > dp1(k + 1, vector<double>(n)), dp2;

	dp2 = dp1;

	dp1[k][p - 1] = 1;

	for(int g = h - 1; g >= 0; --g){

		if(v[g] == -1){

			dp2[0] = dp1[0];

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

				double pr1 = (double)i / rst;

				double pr2 = pr1 / (n - 1);

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

					dp2[i][j] = dp1[i][j] * (1 - pr1);

				}

				dp2[i - 1][0] += (dp1[i][0] * (n - 2) + dp1[i][1]) * pr2;

				dp2[i - 1][n - 1] += (dp1[i][n - 1] * (n - 2) + dp1[i][n - 2]) * pr2;

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

					dp2[i - 1][j] += (dp1[i][j] * (n - 3) + dp1[i][j - 1] + dp1[i][j + 1]) * pr2;

				}

			}

			dp1.swap(dp2);

			--rst;

		}

		else{

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

				swap(dp1[i][v[g]], dp1[i][v[g] + 1]);

			}

		}

	}

	double ans = *max_element(dp1[0].begin(), dp1[0].end());

	printf("%.9f\n", ans);

}

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

#include<cstring>

#include<cstdlib>

using namespace std;

int maps[1005][1005];

int main() {

	int h,w,a,b;

	cin>>h>>w>>a>>b;

	memset(maps,0,sizeof(maps));

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

		for(int j=a+1; j<=w; j++) {

			maps[i][j]=1;

		}

	}

	for(int i=b+1; i<=h; i++) {

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

			maps[i][j]=1;

		}

	}

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

		for(int j=1; j<=w; j++)cout<<maps[i][j];

		cout<<'\n';

	}

	return 0;

}

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



using namespace std;



int main(){

    int H, W, A, B;

    cin >> H >> W >> A >> B;

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

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

            if((i<=B && j<=A) || (i>B && j>A)){

                cout << 0;

            } else{

                cout << 1;

            }

        }

        cout << endl;

    }

    

}

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

#define maxn 800

#define maxm 1009

using namespace std;

int b[maxn][maxn],a[maxn][maxn];

int  guass(int n)

{

	int i,j,p,row=0,col=0;

	for(;row<n&&col<n;row++,col++)

	{

		for(i=row,p=row;i<n;i++)

			if(a[i][col])

			{p=i;break;}

		if(p!=row)

			for(j=col;j<=n;j++)

				swap(a[p][j],a[row][j]);

		if(!a[row][col]) 

		{

			row--;

			continue;

		}

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

			if(a[i][col])

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

				a[i][j]^=a[row][j];

	}

	for(i=row;i<n;i++)

		if(a[i][n]) return 0;

	return 1;

}

int main()

{

	int n,m,d;

	while(scanf("%d%d%d",&m,&n,&d)!=EOF&&n+m+d)

	{

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

		{

			for(int j=0;j<m;j++)

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

		}

		memset(a,0,sizeof(a));

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

		{

			for(int j=0;j<m;j++)

			{

				a[i*m+j][n*m]=b[i][j];

				a[i*m+j][i*m+j]=1;

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

				{

					for(int y=0;y<m;y++)

					{

						if(abs(x-i)+abs(y-j)==d)

							a[i*m+j][x*m+y]=1;

					}

				}

			}

		}

		if(guass(n*m))

			puts("1");

		else

			puts("0");

	}

	return 0;

}

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

#include <cstring>

#include <bitset>

#include <iostream>

#include <cmath>



using namespace std;



int n, m, D;

int a[30][30];

bitset <650> G[650];



inline int id(int x, int y) {

    return x * m + y;

}



bool Gauss(int equ, int var) {

    int col = 0, k;

    for(k = 0; k < equ && col < var; ++k, ++col) {

        if(!G[k][col]) {

            for(int i = k + 1; i < equ; ++i) if(G[i][col]) {

                G[k] ^= G[i];

                break;

            }

        }

        if(!G[k][col]) {

            k--;

            continue;

        }

        for(int i = k + 1; i < equ; ++i) 

			if(G[i][col]) 

				G[i] ^= G[k];

    }

    for(int i = k; i < equ; ++i) 

		if(G[i][var]) 

			return 0;

    return 1;

}



int main() {

    while(scanf("%d%d%d", &m, &n, &D)) {

        if(n == 0) break;

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

			for(int j = 0; j < m; ++j) 

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

        int U = n * m;

        for(int i = 0; i < U; ++i) G[i].reset();

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

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

	            int u = id(i, j);

	            G[u][u] = 1;

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

					for(int y = 0; y < m; ++y) {

		                if(abs(x - i) + abs(y - j) != D) continue;

		                G[id(x, y)][u] = 1;

		            }

        }

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

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

            if(!a[i][j]) continue;

            G[id(i, j)][n * m] = 1;

        }

        puts(Gauss(n * m, n * m) ? "1" : "0");

    }

    return 0;

}

// Fastest known solution for this problem: