QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398069#1882. DrunkardsdeepthoughtAC ✓291ms394552kbC++232.6kb2024-04-24 21:47:302024-04-24 21:47:31

Judging History

你现在查看的是最新测评结果

  • [2024-04-24 21:47:31]
  • 评测
  • 测评结果:AC
  • 用时:291ms
  • 内存:394552kb
  • [2024-04-24 21:47:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template <int MOD> struct modint{
	static const int mod = MOD;
	int v;
	operator int() const {return v;} 
	modint():v(0) {}
	modint(long long _v):v(int(_v%MOD)) {v += (v<0)*MOD;}
	modint& operator+=(modint o) {if((v += o.v) >= MOD) v-= MOD; return *this;}
	modint& operator-=(modint o) {if((v -= o.v) < 0) v+= MOD; return *this;}
	modint& operator*=(modint o) {v = int((long long)v*o.v%MOD); return *this;}
	modint& operator/=(modint o) {return *this *= inv(o);}
	friend modint pow(modint a, long long p) {
		modint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans; }	friend modint inv(modint a) {assert(a.v != 0); return pow(a, MOD-2);}
	friend modint operator+(modint a, modint b) {return a += b;}
	friend modint operator-(modint a, modint b) {return a -= b;}
	friend modint operator*(modint a, modint b) {return a *= b;}
	friend modint operator/(modint a, modint b) {return a /= b;}
};
using mint = modint<(int)998244353>;

int main() {
    
    int n, pp;
    cin >> n >> pp;
    mint stay = (mint)pp * inv((mint)100);
    mint move = (mint)(100 - pp) * inv((mint)100);
    
    vector <int> arr(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    
    mint home_prob = inv(mint(2 * n + 1));
    mint leave_prob = home_prob * (mint)(2 * n);

    mint dp[2 * n + 1][2 * n + 1];

    for(int i = 0; i < 2 * n + 1; i++){
        for(int j = 0; j < 2 * n + 1; j++) {
            dp[i][j] = 0;
        }
    }

    // dp[time][distance]
    // you reach there at least once
    dp[0][n] = (mint) 1; // distance n - n = 0, can go + (n-n)


    for(int time = 1; time <= n; time++) {
        
        for(int distance = 0; distance <= 2 * n; distance++) {
 
            dp[time][distance] = dp[time - 1][distance] * stay;
            
            if(distance > 0) {
                if(arr[time] == 1) {
                    dp[time][distance] += dp[time - 1][distance - 1] * move; 
                }
            }
            
            if(distance < 2 * n) {
                if(arr[time] == -1) {
                    dp[time][distance] += dp[time - 1][distance + 1] * move;
                }
            }
        }
        dp[time][n] = (mint) 1;

    }

    mint answer = (mint) 0;
    for(int i = 0; i <= 2 * n; i++) {
        answer += dp[n][i];
    }
    answer *= home_prob;
    // cout << (dp[2][3]) << endl;

    // cout << (move * stay * (mint) 2 + move*move) << endl;

//   _ _ N _ _

    cout << answer << endl;





}

/*

d.in: 340310575

a.in: 702764025







_ _ _ N _ _ _




*/



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3528kb

input:

2 28
1 1

output:

702764025

result:

ok 1 number(s): "702764025"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

5 50
-1 1 -1 -1 -1

output:

17015529

result:

ok 1 number(s): "17015529"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5 50
-1 1 -1 1 1

output:

680621150

result:

ok 1 number(s): "680621150"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

10 50
1 1 1 1 1 -1 -1 -1 1 1

output:

812744705

result:

ok 1 number(s): "812744705"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

10 50
-1 -1 1 1 -1 -1 1 -1 -1 -1

output:

158575275

result:

ok 1 number(s): "158575275"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

15 65
1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 1

output:

553313087

result:

ok 1 number(s): "553313087"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

15 65
-1 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1

output:

140408188

result:

ok 1 number(s): "140408188"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10 7
1 1 1 1 1 1 1 1 1 1

output:

375530019

result:

ok 1 number(s): "375530019"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

10 73
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

289966217

result:

ok 1 number(s): "289966217"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

10 0
1 1 -1 1 1 1 -1 1 -1 1

output:

95070891

result:

ok 1 number(s): "95070891"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

10 0
1 1 1 -1 1 1 1 1 1 1

output:

570425345

result:

ok 1 number(s): "570425345"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

10 0
-1 1 1 1 -1 1 -1 -1 1 1

output:

475354454

result:

ok 1 number(s): "475354454"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

10 0
-1 -1 -1 -1 -1 -1 1 -1 1 -1

output:

332748118

result:

ok 1 number(s): "332748118"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 0
1 1 1 1 1 1 -1 1 1 1

output:

570425345

result:

ok 1 number(s): "570425345"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

10 0
-1 -1 -1 1 1 1 -1 1 -1 1

output:

475354454

result:

ok 1 number(s): "475354454"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

10 0
-1 1 1 1 1 -1 -1 1 -1 1

output:

95070891

result:

ok 1 number(s): "95070891"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10 100
-1 1 -1 1 1 -1 -1 -1 -1 -1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

10 100
1 1 1 1 1 1 -1 1 1 1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #19:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

10 100
-1 -1 -1 -1 1 1 -1 -1 1 1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

10 27
1 -1 -1 1 -1 -1 1 -1 -1 1

output:

89502877

result:

ok 1 number(s): "89502877"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

10 27
1 1 -1 1 -1 1 1 -1 -1 1

output:

602378374

result:

ok 1 number(s): "602378374"

Test #22:

score: 0
Accepted
time: 257ms
memory: 394284kb

input:

5000 25
1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 -1 -1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 ...

output:

961556565

result:

ok 1 number(s): "961556565"

Test #23:

score: 0
Accepted
time: 240ms
memory: 394288kb

input:

5000 25
1 -1 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 1 -1 -1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 1 ...

output:

234465387

result:

ok 1 number(s): "234465387"

Test #24:

score: 0
Accepted
time: 237ms
memory: 394196kb

input:

5000 25
-1 -1 1 -1 1 1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 1 1 1 -1 -1 1 1 1 1...

output:

836059165

result:

ok 1 number(s): "836059165"

Test #25:

score: 0
Accepted
time: 243ms
memory: 394532kb

input:

5000 25
-1 1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 -1 -1 -1 1 -1 1 1 1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 1 1...

output:

747198137

result:

ok 1 number(s): "747198137"

Test #26:

score: 0
Accepted
time: 231ms
memory: 394312kb

input:

5000 25
1 1 -1 1 -1 1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 -1 -1 1 -1 1 1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 1 1 1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1 1 1 1 -1 1 -1 -1 1 ...

output:

915679440

result:

ok 1 number(s): "915679440"

Test #27:

score: 0
Accepted
time: 239ms
memory: 394248kb

input:

5000 25
-1 1 1 -1 -1 1 -1 1 1 -1 1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1 1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 1 1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 1 1 -1 -1 ...

output:

129598521

result:

ok 1 number(s): "129598521"

Test #28:

score: 0
Accepted
time: 240ms
memory: 394248kb

input:

5000 25
-1 1 1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 -1 1 1 1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 1...

output:

678292635

result:

ok 1 number(s): "678292635"

Test #29:

score: 0
Accepted
time: 239ms
memory: 394472kb

input:

5000 25
-1 -1 -1 1 -1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 -1 1 -1 1 -1 -1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 1 1 -1 1 1 1 1 -1 1 -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 -...

output:

570879180

result:

ok 1 number(s): "570879180"

Test #30:

score: 0
Accepted
time: 238ms
memory: 394352kb

input:

5000 25
-1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 1 1 1 1 -1 1 -1 1 1 1 -1 1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1...

output:

497284899

result:

ok 1 number(s): "497284899"

Test #31:

score: 0
Accepted
time: 249ms
memory: 394312kb

input:

5000 25
1 -1 -1 -1 1 1 -1 1 -1 1 1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 1 1 -1 1 1 -1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 ...

output:

547200460

result:

ok 1 number(s): "547200460"

Test #32:

score: 0
Accepted
time: 255ms
memory: 394304kb

input:

5000 25
-1 1 -1 1 -1 1 1 -1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 1 1 1 1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 1 1 1 1 1 -1 -1 -1 1 1 -1 -1 1 1 1 1 ...

output:

431564537

result:

ok 1 number(s): "431564537"

Test #33:

score: 0
Accepted
time: 240ms
memory: 394544kb

input:

5000 25
-1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 1 1 1 1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 1...

output:

944967577

result:

ok 1 number(s): "944967577"

Test #34:

score: 0
Accepted
time: 246ms
memory: 394192kb

input:

5000 25
-1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 -1 -1 1 -1 1...

output:

205819355

result:

ok 1 number(s): "205819355"

Test #35:

score: 0
Accepted
time: 255ms
memory: 394248kb

input:

5000 25
-1 1 1 -1 1 -1 -1 1 1 -1 1 1 -1 -1 1 1 -1 1 1 -1 -1 -1 1 1 1 1 -1 1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 1...

output:

307666691

result:

ok 1 number(s): "307666691"

Test #36:

score: 0
Accepted
time: 248ms
memory: 394536kb

input:

5000 25
1 -1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 1 1 1 ...

output:

975555440

result:

ok 1 number(s): "975555440"

Test #37:

score: 0
Accepted
time: 247ms
memory: 394256kb

input:

5000 25
-1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 1 1 -1 -1 -...

output:

954115106

result:

ok 1 number(s): "954115106"

Test #38:

score: 0
Accepted
time: 256ms
memory: 394196kb

input:

5000 25
1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 -1 1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -...

output:

20240102

result:

ok 1 number(s): "20240102"

Test #39:

score: 0
Accepted
time: 238ms
memory: 394316kb

input:

5000 25
-1 1 1 -1 1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 1 1 1 -1 1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 1 1 1 -1 -1 -1 1 -1 1 1 -1 ...

output:

888096663

result:

ok 1 number(s): "888096663"

Test #40:

score: 0
Accepted
time: 236ms
memory: 394472kb

input:

5000 25
-1 1 1 1 1 1 1 1 -1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 -1 1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 1 1 1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 1 ...

output:

753978167

result:

ok 1 number(s): "753978167"

Test #41:

score: 0
Accepted
time: 279ms
memory: 394284kb

input:

5000 45
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

377962368

result:

ok 1 number(s): "377962368"

Test #42:

score: 0
Accepted
time: 277ms
memory: 394312kb

input:

5000 45
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 -1 1 1 1 1...

output:

262524907

result:

ok 1 number(s): "262524907"

Test #43:

score: 0
Accepted
time: 291ms
memory: 394248kb

input:

5000 45
1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 ...

output:

684504852

result:

ok 1 number(s): "684504852"

Test #44:

score: 0
Accepted
time: 283ms
memory: 394552kb

input:

5000 45
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 ...

output:

256186185

result:

ok 1 number(s): "256186185"

Test #45:

score: 0
Accepted
time: 271ms
memory: 394284kb

input:

5000 45
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

56452003

result:

ok 1 number(s): "56452003"

Test #46:

score: 0
Accepted
time: 221ms
memory: 394316kb

input:

5000 45
-1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...

output:

353171752

result:

ok 1 number(s): "353171752"

Test #47:

score: 0
Accepted
time: 223ms
memory: 394248kb

input:

5000 45
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -...

output:

494279764

result:

ok 1 number(s): "494279764"

Test #48:

score: 0
Accepted
time: 212ms
memory: 394288kb

input:

5000 45
-1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...

output:

863796400

result:

ok 1 number(s): "863796400"

Test #49:

score: 0
Accepted
time: 212ms
memory: 394280kb

input:

5000 45
-1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...

output:

883427667

result:

ok 1 number(s): "883427667"

Test #50:

score: 0
Accepted
time: 228ms
memory: 394472kb

input:

5000 45
1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 ...

output:

435945626

result:

ok 1 number(s): "435945626"

Test #51:

score: 0
Accepted
time: 227ms
memory: 394512kb

input:

5000 64
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...

output:

144231886

result:

ok 1 number(s): "144231886"

Test #52:

score: 0
Accepted
time: 284ms
memory: 394220kb

input:

5000 43
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

448366527

result:

ok 1 number(s): "448366527"

Test #53:

score: 0
Accepted
time: 208ms
memory: 394312kb

input:

5000 0
-1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 1 1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 1 1 -1 1 -1 1 1 -1 1 1 -1 -1 -1 1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 1 -1 -1 1 1 1 1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 ...

output:

961512634

result:

ok 1 number(s): "961512634"

Test #54:

score: 0
Accepted
time: 218ms
memory: 394312kb

input:

5000 0
-1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 1 1 1 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 1 -1 -1 1 1 1 -1 1...

output:

356936487

result:

ok 1 number(s): "356936487"

Test #55:

score: 0
Accepted
time: 224ms
memory: 394312kb

input:

5000 0
1 -1 -1 1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 1 1 1 1 ...

output:

973390554

result:

ok 1 number(s): "973390554"

Test #56:

score: 0
Accepted
time: 212ms
memory: 394248kb

input:

5000 100
-1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 1 1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 ...

output:

906315241

result:

ok 1 number(s): "906315241"

Test #57:

score: 0
Accepted
time: 208ms
memory: 394312kb

input:

5000 100
1 1 1 1 -1 1 1 1 1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 -1 -1 1 1 1 1 1 -1 1 -1 1 -1 -1 1 -1 1 1 1 -1 -1 1 1 1 -1 -1 1 -1 1 1 1 1 1 1 -1 -1 -1 1 -1 1 1 -1 -1 ...

output:

906315241

result:

ok 1 number(s): "906315241"

Test #58:

score: 0
Accepted
time: 211ms
memory: 394316kb

input:

5000 100
1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 1 -1...

output:

906315241

result:

ok 1 number(s): "906315241"

Test #59:

score: 0
Accepted
time: 216ms
memory: 394244kb

input:

5000 100
-1 1 1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 1 -1 1 1 1 -1 1 -1 -1 1 1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 -1 1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -...

output:

906315241

result:

ok 1 number(s): "906315241"

Test #60:

score: 0
Accepted
time: 205ms
memory: 394320kb

input:

5000 100
1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 1 1 1 1 -1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 1 ...

output:

906315241

result:

ok 1 number(s): "906315241"

Test #61:

score: 0
Accepted
time: 241ms
memory: 394004kb

input:

4998 5
-1 1 -1 1 -1 1 -1 1 1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 -1 1 1 -1 1...

output:

335960136

result:

ok 1 number(s): "335960136"

Test #62:

score: 0
Accepted
time: 230ms
memory: 394000kb

input:

4998 5
1 1 -1 1 1 -1 1 1 -1 -1 1 1 1 -1 1 1 -1 1 1 -1 -1 1 1 1 1 -1 1 -1 -1 1 1 -1 1 1 -1 1 -1 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 1 1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 ...

output:

931188852

result:

ok 1 number(s): "931188852"

Test #63:

score: 0
Accepted
time: 255ms
memory: 394036kb

input:

4998 5
1 -1 1 1 -1 1 1 1 -1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 -1 1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1...

output:

747827219

result:

ok 1 number(s): "747827219"

Test #64:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

1 9
-1

output:

176356503

result:

ok 1 number(s): "176356503"

Test #65:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

2 69
-1 1

output:

857232356

result:

ok 1 number(s): "857232356"

Test #66:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

3 63
-1 -1 1

output:

296264521

result:

ok 1 number(s): "296264521"