1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
#include <algorithm>
#include <cstdio>
#include <vector>

#ifdef LOCAL
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

typedef vector<int> V;

bool only0(V& v) {
    for (int i = 0; i < v.size(); ++i) {
        if (v[i] != 0) return false;
    }
    return true;
}
bool only1(V& v) {
    for (int i = 0; i < v.size(); ++i) {
        if (v[i] != 1) return false;
    }
    return true;
}

V groups(V& v) {
    int groupsize = 0;
    V grps;

    for (int i = 0; i < v.size(); ++i) {
        if (v[i] == 0) {
            if (groupsize > 0) {
                grps.push_back(groupsize);
                groupsize = 0;
            }
        } else {
            groupsize++;
        }
    }
    if (groupsize > 0) {
        if (grps.empty() || v[0] == 0) {
            grps.push_back(groupsize);
        } else {
            grps[0] += groupsize;
        }
    }
    ranges::sort(grps);
    return grps;
}

int get_response_2(V& v, int o, int e) {
    if (e == 0) return 1;
    if (o == 1) return 2;
    return 0;
}

int get_response_4(V& v, int o, int e) {
    if (only0(v)) return 540;
    if (only1(v)) return 720;
    if (o == 1 && e == 0) return 54;
    if (o == 2 && e == 0) return 24;
    if (o == 2 && e == 1) return 114;
    return 0;
}

int get_response_6(V& v, int o, int e) {
    V grps = groups(v);
    if (only0(v)) return 1701000;
    if (only1(v)) return 2041200;
    if (o == 1 && e == 0) return 63000;
    if (o == 2 && e == 0) return 8640;
    if (o == 2 && e == 1 && grps == V{3}) return 108360;
    if (o == 3 && e == 0) return 1080;
    if (o == 3 && e == 1) return 11160;
    if (o == 3 && e == 2) return 148680;
    return 0;
}

int get_response_8(V& v, int o, int e) {
    V grps = groups(v);
    if (only0(v)) return 70251067;
    if (only1(v)) return 794572653;

    if (o == 1 && e == 0) return 366735600;
    if (o == 2 && e == 0) return 24494400;
    if (o == 2 && e == 1 && grps == V{3}) return 561330000;
    if (o == 3 && e == 0) return 1260000;
    if (o == 3 && e == 1 && grps == V{1,3}) return 29484000;
    if (o == 4 && e == 0) return 80640;
    if (o == 3 && e == 2 && grps == V{5}) return 740955600;
    if (o == 4 && e == 1) return 1441440;
    if (o == 4 && e == 2 && grps == V{3,3}) return 34473600;
    if (o == 4 && e == 2 && grps == V{1,5}) return 34020000;
    if (o == 4 && e == 3) return 905612400;
    return 0;
}

int get_response_10(V& v, int o, int e) {
    V grps = groups(v);
    if (only0(v)) return 622541044;
    if (only1(v)) return 802823383;

    if (o == 1 && e == 0) return 101441660;
    if (o == 2 && e == 0) return 534871773;
    if (o == 2 && e == 1 && grps == V{3}) return 909454214;
    if (o == 3 && e == 0) return 334711951;
    if (o == 3 && e == 1 && grps == V{1,3}) return 399695486;
    if (o == 4 && e == 0) return 228614400;
    if (o == 3 && e == 2 && grps == V{5}) return 258171902;
    if (o == 4 && e == 1 && grps == V{1,1,3}) return 113089544;
    if (o == 5 && e == 0) return 9072000;
    if (o == 4 && e == 2 && grps == V{3,3}) return 264519199;
    if (o == 4 && e == 2 && grps == V{1,5}) return 540197620;
    if (o == 5 && e == 1 && grps == V{1,1,1,3}) return 248572800;
    if (o == 4 && e == 3 && grps == V{7}) return 147594738;
    if (o == 5 && e == 2 && grps == V{1,1,5}) return 831591944;
    if (o == 5 && e == 2 && grps == V{1,3,3}) return 891467144;
    if (o == 5 && e == 3 && grps == V{1,7}) return 956378175;
    if (o == 5 && e == 3 && grps == V{3,5}) return 405021333;
    if (o == 5 && e == 4) return 577722722;

    return 0;
}

int get_response_12(V& v, int o, int e) {
    V grps = groups(v);
    if (only0(v)) return 211803850;
    if (only1(v)) return 321967837;

    if (o == 1 && e == 0) return 938188926;
    if (o == 2 && e == 0) return 633880533;
    if (o == 2 && e == 1 && grps == V{3}) return 668799954;
    if (o == 3 && e == 0) return 28833186;
    if (o == 3 && e == 1 && grps == V{1,3}) return 974172069;
    if (o == 4 && e == 0) return 992136520;
    if (o == 3 && e == 2 && grps == V{5}) return 697953316;
    if (o == 4 && e == 1 && grps == V{1,1,3}) return 260883381;
    if (o == 5 && e == 0) return 809926036;
    if (o == 4 && e == 2 && grps == V{3,3}) return 314463598;
    if (o == 4 && e == 2 && grps == V{1,5}) return 770237731;
    if (o == 5 && e == 1 && grps == V{1,1,1,3}) return 451431372;
    if (o == 6 && e == 0) return 437004793;
    if (o == 4 && e == 3 && grps == V{7}) return 25649005;
    if (o == 5 && e == 2 && grps == V{1,1,5}) return 655754154;
    if (o == 5 && e == 2 && grps == V{1,3,3}) return 492933576;
    if (o == 6 && e == 1 && grps == V{1,1,1,1,3}) return 923436415;
    if (o == 5 && e == 3 && grps == V{1,7}) return 22077519;
    if (o == 5 && e == 3 && grps == V{3,5}) return 110529260;
    if (o == 6 && e == 2 && grps == V{1,1,1,5}) return 13439901;
    if (o == 6 && e == 2 && grps == V{1,1,3,3}) return 910726231;
    if (o == 5 && e == 4 && grps == V{9}) return 651887035;
    if (o == 6 && e == 3 && grps == V{1,1,7}) return 213445498;
    if (o == 6 && e == 3 && grps == V{3,3,3}) return 724983771;
    if (o == 6 && e == 3 && grps == V{1,3,5}) return 887804349;
    if (o == 6 && e == 4 && grps == V{3,7}) return 362369055;
    if (o == 6 && e == 4 && grps == V{1,9}) return 729691447;
    if (o == 6 && e == 4 && grps == V{5,5}) return 906594929;
    if (o == 6 && e == 5) return 576667392;

    return 0;
}

int get_response_14(V& v, int o, int e) {
    V grps = groups(v);
    if (only0(v)) return 595065046;
    if (only1(v)) return 256223893;

    if (o == 1 && e == 0) return 414828946;
    if (o == 2 && e == 0) return 863614023;
    if (o == 2 && e == 1 && grps == V{3}) return 791997275;
    if (o == 3 && e == 0) return 763778394;
    if (o == 3 && e == 1 && grps == V{1,3}) return 552795143;
    if (o == 4 && e == 0) return 916218273;
    if (o == 3 && e == 2 && grps == V{5}) return 34078863;
    if (o == 4 && e == 1 && grps == V{1,1,3}) return 686222513;
    if (o == 5 && e == 0) return 607598942;
    if (o == 4 && e == 2 && grps == V{3,3}) return 241976263;
    if (o == 4 && e == 2 && grps == V{1,5}) return 168533605;
    if (o == 5 && e == 1 && grps == V{1,1,1,3}) return 277384403;
    if (o == 6 && e == 0) return 379143799;
    if (o == 4 && e == 3 && grps == V{7}) return 141073724;
    if (o == 5 && e == 2 && grps == V{1,1,5}) return 802835961;
    if (o == 5 && e == 2 && grps == V{1,3,3}) return 608666632;
    if (o == 6 && e == 1 && grps == V{1,1,1,1,3}) return 535799715;
    if (o == 7 && e == 0) return 124017065;
    if (o == 5 && e == 3 && grps == V{1,7}) return 710829416;
    if (o == 5 && e == 3 && grps == V{3,5}) return 857714732;
    if (o == 6 && e == 2 && grps == V{1,1,1,5}) return 461647058;
    if (o == 6 && e == 2 && grps == V{1,1,3,3}) return 638550540;
    if (o == 7 && e == 1 && grps == V{1,1,1,1,1,3}) return 216323221;
    if (o == 5 && e == 4 && grps == V{9}) return 112981851;
    if (o == 6 && e == 3 && grps == V{1,1,7}) return 113618731;
    if (o == 6 && e == 3 && grps == V{3,3,3}) return 531110751;
    if (o == 6 && e == 3 && grps == V{1,3,5}) return 725280080;
    if (o == 7 && e == 2 && grps == V{1,1,1,1,5}) return 115282793;
    if (o == 7 && e == 2 && grps == V{1,1,1,3,3}) return 464000488;
    if (o == 6 && e == 4 && grps == V{3,7}) return 400010536;
    if (o == 6 && e == 4 && grps == V{1,9}) return 179682562;
    if (o == 6 && e == 4 && grps == V{5,5}) return 473453194;
    if (o == 7 && e == 3 && grps == V{1,1,1,7}) return 469006231;
    if (o == 7 && e == 3 && grps == V{1,1,3,5}) return 822813195;
    if (o == 7 && e == 3 && grps == V{1,3,3,3}) return 999716677;
    if (o == 6 && e == 5 && grps == V{11}) return 949803251;
    if (o == 7 && e == 4 && grps == V{1,3,7}) return 36062850;
    if (o == 7 && e == 4 && grps == V{1,1,9}) return 618570837;
    if (o == 7 && e == 4 && grps == V{3,3,5}) return 647724199;
    if (o == 7 && e == 4 && grps == V{1,5,5}) return 841893528;
    if (o == 7 && e == 5 && grps == V{5,7}) return 15748998;
    if (o == 7 && e == 5 && grps == V{1,11}) return 575093057;
    if (o == 7 && e == 5 && grps == V{3,9}) return 868863689;
    if (o == 7 && e == 6 && grps == V{13}) return 651537910;
    return 0;
}

int get_response_16(V& v, int o, int e) {
    V grps = groups(v);
    if (o == 0 && e == 0 && grps == V{}) return 564609482;
    if (o == 1 && e == 0 && grps == V{1}) return 80019869;
    if (o == 2 && e == 0 && grps == V{1,1}) return 74686695;
    if (o == 2 && e == 1 && grps == V{3}) return 829536107;
    if (o == 3 && e == 0 && grps == V{1,1,1}) return 296578864;
    if (o == 3 && e == 1 && grps == V{1,3}) return 846851805;
    if (o == 4 && e == 0 && grps == V{1,1,1,1}) return 60397492;
    if (o == 3 && e == 2 && grps == V{5}) return 173896603;
    if (o == 4 && e == 1 && grps == V{1,1,3}) return 805252173;
    if (o == 5 && e == 0 && grps == V{1,1,1,1,1}) return 99204399;
    if (o == 4 && e == 2 && grps == V{3,3}) return 619016908;
    if (o == 4 && e == 2 && grps == V{1,5}) return 812640424;
    if (o == 5 && e == 1 && grps == V{1,1,1,3}) return 817121986;
    if (o == 6 && e == 0 && grps == V{1,1,1,1,1,1}) return 187657677;
    if (o == 4 && e == 3 && grps == V{7}) return 113101371;
    if (o == 5 && e == 2 && grps == V{1,3,3}) return 313925475;
    if (o == 5 && e == 2 && grps == V{1,1,5}) return 773578546;
    if (o == 6 && e == 1 && grps == V{1,1,1,1,3}) return 788980882;
    if (o == 7 && e == 0 && grps == V{1,1,1,1,1,1,1}) return 399460532;
    if (o == 5 && e == 3 && grps == V{3,5}) return 584805527;
    if (o == 5 && e == 3 && grps == V{1,7}) return 972052559;
    if (o == 6 && e == 2 && grps == V{1,1,1,5}) return 280075841;
    if (o == 6 && e == 2 && grps == V{1,1,3,3}) return 573846473;
    if (o == 7 && e == 1 && grps == V{1,1,1,1,1,3}) return 632322218;
    if (o == 8 && e == 0 && grps == V{1,1,1,1,1,1,1,1}) return 158966163;
    if (o == 5 && e == 4 && grps == V{9}) return 647150411;
    if (o == 6 && e == 3 && grps == V{1,1,7}) return 201557983;
    if (o == 6 && e == 3 && grps == V{1,3,5}) return 282251848;
    if (o == 6 && e == 3 && grps == V{3,3,3}) return 822598784;
    if (o == 7 && e == 2 && grps == V{1,1,1,1,5}) return 255434667;
    if (o == 7 && e == 2 && grps == V{1,1,1,3,3}) return 478757358;
    if (o == 8 && e == 1 && grps == V{1,1,1,1,1,1,3}) return 112263624;
    if (o == 6 && e == 4 && grps == V{1,9}) return 325088203;
    if (o == 6 && e == 4 && grps == V{5,5}) return 550594146;
    if (o == 6 && e == 4 && grps == V{3,7}) return 744217662;
    if (o == 7 && e == 3 && grps == V{1,1,3,5}) return 36800328;
    if (o == 7 && e == 3 && grps == V{1,3,3,3}) return 330570960;
    if (o == 7 && e == 3 && grps == V{1,1,1,7}) return 449259071;
    if (o == 8 && e == 2 && grps == V{1,1,1,1,3,3}) return 76986752;
    if (o == 8 && e == 2 && grps == V{1,1,1,1,1,5}) return 369372831;
    if (o == 6 && e == 5 && grps == V{11}) return 776043716;
    if (o == 7 && e == 4 && grps == V{1,1,9}) return 89190491;
    if (o == 7 && e == 4 && grps == V{1,5,5}) return 250578221;
    if (o == 7 && e == 4 && grps == V{1,3,7}) return 710231292;
    if (o == 7 && e == 4 && grps == V{3,3,5}) return 790925157;
    if (o == 8 && e == 3 && grps == V{1,1,3,3,3}) return 168533834;
    if (o == 8 && e == 3 && grps == V{1,1,1,1,7}) return 498565768;
    if (o == 8 && e == 3 && grps == V{1,1,1,3,5}) return 945211150;
    if (o == 7 && e == 5 && grps == V{3,9}) return 97253306;
    if (o == 7 && e == 5 && grps == V{5,7}) return 710006281;
    if (o == 7 && e == 5 && grps == V{1,11}) return 871747370;
    if (o == 8 && e == 4 && grps == V{3,3,3,3}) return 87295447;
    if (o == 8 && e == 4 && grps == V{1,1,3,7}) return 205983558;
    if (o == 8 && e == 4 && grps == V{1,1,1,9}) return 324671669;
    if (o == 8 && e == 4 && grps == V{1,1,5,5}) return 499754190;
    if (o == 8 && e == 4 && grps == V{1,3,3,5}) return 793524822;
    if (o == 7 && e == 6 && grps == V{13}) return 499781286;
    if (o == 8 && e == 5 && grps == V{3,3,7}) return 218904594;
    if (o == 8 && e == 5 && grps == V{1,1,11}) return 436476070;
    if (o == 8 && e == 5 && grps == V{1,3,9}) return 597863800;
    if (o == 8 && e == 5 && grps == V{1,5,7}) return 678557665;
    if (o == 8 && e == 5 && grps == V{3,5,5}) return 759251530;
    if (o == 8 && e == 6 && grps == V{5,9}) return 63041925;
    if (o == 8 && e == 6 && grps == V{1,13}) return 612030046;
    if (o == 8 && e == 6 && grps == V{3,11}) return 643912473;
    if (o == 8 && e == 6 && grps == V{7,7}) return 869418416;
    if (o == 8 && e == 7 && grps == V{15}) return 818363128;
    if (o == 8 && e == 8 && grps == V{16}) return 535583447;
    return 0;
}


int get_response_18(V& v, int o, int e) {
    V grps = groups(v);
    if (o == 0 && e == 0 && grps == V{}) return 718027659;
    if (o == 1 && e == 0 && grps == V{1}) return 911508517;
    if (o == 2 && e == 0 && grps == V{1,1}) return 427001322;
    if (o == 2 && e == 1 && grps == V{3}) return 136974123;
    if (o == 3 && e == 0 && grps == V{1,1,1}) return 600397373;
    if (o == 3 && e == 1 && grps == V{1,3}) return 477097783;
    if (o == 4 && e == 0 && grps == V{1,1,1,1}) return 697075820;
    if (o == 3 && e == 2 && grps == V{5}) return 961668055;
    if (o == 4 && e == 1 && grps == V{1,1,3}) return 598462304;
    if (o == 5 && e == 0 && grps == V{1,1,1,1,1}) return 735367811;
    if (o == 4 && e == 2 && grps == V{1,5}) return 41707258;
    if (o == 4 && e == 2 && grps == V{3,3}) return 527194244;
    if (o == 5 && e == 1 && grps == V{1,1,1,3}) return 785736239;
    if (o == 6 && e == 0 && grps == V{1,1,1,1,1,1}) return 665355666;
    if (o == 4 && e == 3 && grps == V{7}) return 385590292;
    if (o == 5 && e == 2 && grps == V{1,3,3}) return 596527235;
    if (o == 5 && e == 2 && grps == V{1,1,5}) return 975904309;
    if (o == 6 && e == 1 && grps == V{1,1,1,1,3}) return 770061033;
    if (o == 7 && e == 0 && grps == V{1,1,1,1,1,1,1}) return 573180972;
    if (o == 5 && e == 3 && grps == V{3,5}) return 91803719;
    if (o == 5 && e == 3 && grps == V{1,7}) return 120829754;
    if (o == 6 && e == 2 && grps == V{1,1,1,5}) return 648890715;
    if (o == 6 && e == 2 && grps == V{1,1,3,3}) return 874396658;
    if (o == 7 && e == 1 && grps == V{1,1,1,1,1,3}) return 692253621;
    if (o == 8 && e == 0 && grps == V{1,1,1,1,1,1,1,1}) return 841769146;
    if (o == 5 && e == 4 && grps == V{9}) return 408740848;
    if (o == 6 && e == 3 && grps == V{3,3,3}) return 594592166;
    if (o == 6 && e == 3 && grps == V{1,1,7}) return 732723381;
    if (o == 6 && e == 3 && grps == V{1,3,5}) return 973969240;
    if (o == 7 && e == 2 && grps == V{1,1,1,1,5}) return 643366525;
    if (o == 7 && e == 2 && grps == V{1,1,1,3,3}) return 804754255;
    if (o == 8 && e == 1 && grps == V{1,1,1,1,1,1,3}) return 332286883;
    if (o == 9 && e == 0 && grps == V{1,1,1,1,1,1,1,1,1}) return 474101233;
    if (o == 6 && e == 4 && grps == V{3,7}) return 170926215;
    if (o == 6 && e == 4 && grps == V{5,5}) return 656413201;
    if (o == 6 && e == 4 && grps == V{1,9}) return 714465271;
    if (o == 7 && e == 3 && grps == V{1,1,1,7}) return 286539248;
    if (o == 7 && e == 3 && grps == V{1,1,3,5}) return 737551134;
    if (o == 7 && e == 3 && grps == V{1,3,3,3}) return 963057077;
    if (o == 8 && e == 2 && grps == V{1,1,1,1,1,5}) return 544069055;
    if (o == 8 && e == 2 && grps == V{1,1,1,1,3,3}) return 719151576;
    if (o == 9 && e == 1 && grps == V{1,1,1,1,1,1,1,3}) return 620427296;
    if (o == 6 && e == 5 && grps == V{11}) return 31119716;
    if (o == 7 && e == 4 && grps == V{1,5,5}) return 351411238;
    if (o == 7 && e == 4 && grps == V{1,3,7}) return 730788312;
    if (o == 7 && e == 4 && grps == V{1,1,9}) return 868919527;
    if (o == 7 && e == 4 && grps == V{3,3,5}) return 972034171;
    if (o == 8 && e == 3 && grps == V{1,1,1,1,7}) return 355284287;
    if (o == 8 && e == 3 && grps == V{1,1,1,3,5}) return 678059747;
    if (o == 8 && e == 3 && grps == V{1,1,3,3,3}) return 839447477;
    if (o == 9 && e == 2 && grps == V{1,1,1,1,1,3,3}) return 91392794;
    if (o == 9 && e == 2 && grps == V{1,1,1,1,1,1,5}) return 198102037;
    if (o == 7 && e == 5 && grps == V{5,7}) return 735535697;
    if (o == 7 && e == 5 && grps == V{3,9}) return 764561732;
    if (o == 7 && e == 5 && grps == V{1,11}) return 822613802;
    if (o == 8 && e == 4 && grps == V{3,3,3,3}) return 51717489;
    if (o == 8 && e == 4 && grps == V{1,1,3,7}) return 375199667;
    if (o == 8 && e == 4 && grps == V{1,1,5,5}) return 600705610;
    if (o == 8 && e == 4 && grps == V{1,1,1,9}) return 698681845;
    if (o == 8 && e == 4 && grps == V{1,3,3,5}) return 826211553;
    if (o == 9 && e == 3 && grps == V{1,1,1,1,1,7}) return 220801968;
    if (o == 9 && e == 3 && grps == V{1,1,1,1,3,5}) return 570967010;
    if (o == 9 && e == 3 && grps == V{1,1,1,3,3,3}) return 746049531;
    if (o == 7 && e == 6 && grps == V{13}) return 252726903;
    if (o == 8 && e == 5 && grps == V{1,5,7}) return 108230310;
    if (o == 8 && e == 5 && grps == V{3,5,5}) return 349476169;
    if (o == 8 && e == 5 && grps == V{1,1,11}) return 384492740;
    if (o == 8 && e == 5 && grps == V{3,3,7}) return 728853243;
    if (o == 8 && e == 5 && grps == V{1,3,9}) return 866984458;
    if (o == 9 && e == 4 && grps == V{1,1,1,3,7}) return 389977509;
    if (o == 9 && e == 4 && grps == V{1,1,1,5,5}) return 551365239;
    if (o == 9 && e == 4 && grps == V{1,1,3,3,5}) return 712752969;
    if (o == 9 && e == 4 && grps == V{1,3,3,3,3}) return 874140699;
    if (o == 9 && e == 4 && grps == V{1,1,1,1,9}) return 905814326;
    if (o == 8 && e == 6 && grps == V{5,9}) return 329171207;
    if (o == 8 && e == 6 && grps == V{1,13}) return 445275347;
    if (o == 8 && e == 6 && grps == V{7,7}) return 814658193;
    if (o == 8 && e == 6 && grps == V{3,11}) return 872710263;
    if (o == 9 && e == 5 && grps == V{1,1,5,7}) return 238354143;
    if (o == 9 && e == 5 && grps == V{1,3,3,7}) return 463860086;
    if (o == 9 && e == 5 && grps == V{1,3,5,5}) return 689366029;
    if (o == 9 && e == 5 && grps == V{1,1,3,9}) return 787342264;
    if (o == 9 && e == 5 && grps == V{1,1,1,11}) return 885318499;
    if (o == 9 && e == 5 && grps == V{3,3,3,5}) return 914871972;
    if (o == 8 && e == 7 && grps == V{15}) return 73562402;
    if (o == 9 && e == 6 && grps == V{3,5,7}) return 106295241;
    if (o == 9 && e == 6 && grps == V{1,5,9}) return 244426456;
    if (o == 9 && e == 6 && grps == V{1,1,13}) return 279443027;
    if (o == 9 && e == 6 && grps == V{1,3,11}) return 382557671;
    if (o == 9 && e == 6 && grps == V{5,5,5}) return 726918174;
    if (o == 9 && e == 6 && grps == V{1,7,7}) return 865049389;
    if (o == 9 && e == 7 && grps == V{7,9}) return 408293703;
    if (o == 9 && e == 7 && grps == V{5,11}) return 437319738;
    if (o == 9 && e == 7 && grps == V{3,13}) return 495371808;
    if (o == 9 && e == 7 && grps == V{1,15}) return 582449913;
    if (o == 9 && e == 8 && grps == V{17}) return 493626220;
    if (o == 9 && e == 9 && grps == V{18}) return 466146931;
    return 0;
}

int get_response_20(V& v, int o, int e) {
    V grps = groups(v);
    if (o == 0 && e == 0 && grps == V{}) return 397758220;
    if (o == 1 && e == 0 && grps == V{1}) return 974048002;
    if (o == 2 && e == 0 && grps == V{1,1}) return 593763137;
    if (o == 2 && e == 1 && grps == V{3}) return 231886090;
    if (o == 3 && e == 0 && grps == V{1,1,1}) return 230170214;
    if (o == 3 && e == 1 && grps == V{1,3}) return 897840731;
    if (o == 4 && e == 0 && grps == V{1,1,1,1}) return 985345651;
    if (o == 3 && e == 2 && grps == V{5}) return 753025860;
    if (o == 4 && e == 1 && grps == V{1,1,3}) return 132032659;
    if (o == 5 && e == 0 && grps == V{1,1,1,1,1}) return 522861059;
    if (o == 4 && e == 2 && grps == V{3,3}) return 201918318;
    if (o == 4 && e == 2 && grps == V{1,5}) return 536087532;
    if (o == 5 && e == 1 && grps == V{1,1,1,3}) return 185731488;
    if (o == 6 && e == 0 && grps == V{1,1,1,1,1,1}) return 381619412;
    if (o == 4 && e == 3 && grps == V{7}) return 537467298;
    if (o == 5 && e == 2 && grps == V{1,3,3}) return 33895104;
    if (o == 5 && e == 2 && grps == V{1,1,5}) return 430808366;
    if (o == 6 && e == 1 && grps == V{1,1,1,1,3}) return 515120783;
    if (o == 7 && e == 0 && grps == V{1,1,1,1,1,1,1}) return 137680657;
    if (o == 5 && e == 3 && grps == V{1,7}) return 508503547;
    if (o == 5 && e == 3 && grps == V{3,5}) return 840165126;
    if (o == 6 && e == 2 && grps == V{1,1,3,3}) return 386117332;
    if (o == 6 && e == 2 && grps == V{1,1,1,5}) return 444169402;
    if (o == 7 && e == 1 && grps == V{1,1,1,1,1,3}) return 736261088;
    if (o == 8 && e == 0 && grps == V{1,1,1,1,1,1,1,1}) return 356485428;
    if (o == 5 && e == 4 && grps == V{9}) return 585210411;
    if (o == 6 && e == 3 && grps == V{1,1,7}) return 126497328;
    if (o == 6 && e == 3 && grps == V{1,3,5}) return 332670811;
    if (o == 6 && e == 3 && grps == V{3,3,3}) return 935757556;
    if (o == 7 && e == 2 && grps == V{1,1,1,1,5}) return 24888789;
    if (o == 7 && e == 2 && grps == V{1,1,1,3,3}) return 507380507;
    if (o == 8 && e == 1 && grps == V{1,1,1,1,1,1,3}) return 276453545;
    if (o == 9 && e == 0 && grps == V{1,1,1,1,1,1,1,1,1}) return 998177378;
    if (o == 6 && e == 4 && grps == V{5,5}) return 478411927;
    if (o == 6 && e == 4 && grps == V{3,7}) return 812581141;
    if (o == 6 && e == 4 && grps == V{1,9}) return 815088776;
    if (o == 7 && e == 3 && grps == V{1,3,3,3}) return 586503176;
    if (o == 7 && e == 3 && grps == V{1,1,3,5}) return 644555246;
    if (o == 7 && e == 3 && grps == V{1,1,1,7}) return 760659386;
    if (o == 8 && e == 2 && grps == V{1,1,1,1,3,3}) return 90902757;
    if (o == 8 && e == 2 && grps == V{1,1,1,1,1,5}) return 188878992;
    if (o == 9 && e == 1 && grps == V{1,1,1,1,1,1,1,3}) return 464077248;
    if (o == 10 && e == 0 && grps == V{1,1,1,1,1,1,1,1,1,1}) return 731630315;
    if (o == 6 && e == 5 && grps == V{11}) return 896255199;
    if (o == 7 && e == 4 && grps == V{1,3,7}) return 28359773;
    if (o == 7 && e == 4 && grps == V{1,1,9}) return 219099552;
    if (o == 7 && e == 4 && grps == V{3,3,5}) return 234533256;
    if (o == 7 && e == 4 && grps == V{1,5,5}) return 631446518;
    if (o == 8 && e == 3 && grps == V{1,1,1,3,5}) return 17148513;
    if (o == 8 && e == 3 && grps == V{1,1,1,1,7}) return 52165084;
    if (o == 8 && e == 3 && grps == V{1,1,3,3,3}) return 499640231;
    if (o == 9 && e == 2 && grps == V{1,1,1,1,1,3,3}) return 415226433;
    if (o == 9 && e == 2 && grps == V{1,1,1,1,1,1,5}) return 769675520;
    if (o == 10 && e == 1 && grps == V{1,1,1,1,1,1,1,1,3}) return 34601022;
    if (o == 7 && e == 5 && grps == V{3,9}) return 119166363;
    if (o == 7 && e == 5 && grps == V{5,7}) return 450827942;
    if (o == 7 && e == 5 && grps == V{1,11}) return 455843212;
    if (o == 8 && e == 4 && grps == V{1,1,1,9}) return 135201433;
    if (o == 8 && e == 4 && grps == V{3,3,3,3}) return 786889020;
    if (o == 8 && e == 4 && grps == V{1,3,3,5}) return 844941090;
    if (o == 8 && e == 4 && grps == V{1,1,5,5}) return 902993160;
    if (o == 8 && e == 4 && grps == V{1,1,3,7}) return 961045230;
    if (o == 9 && e == 3 && grps == V{1,1,1,3,3,3}) return 445544433;
    if (o == 9 && e == 3 && grps == V{1,1,1,1,3,5}) return 543520668;
    if (o == 9 && e == 3 && grps == V{1,1,1,1,1,7}) return 739473138;
    if (o == 10 && e == 2 && grps == V{1,1,1,1,1,1,3,3}) return 571669068;
    if (o == 10 && e == 2 && grps == V{1,1,1,1,1,1,1,5}) return 871338991;
    if (o == 7 && e == 6 && grps == V{13}) return 470601655;
    if (o == 8 && e == 5 && grps == V{1,3,9}) return 120961997;
    if (o == 8 && e == 5 && grps == V{1,5,7}) return 327135480;
    if (o == 8 && e == 5 && grps == V{3,5,5}) return 533308963;
    if (o == 8 && e == 5 && grps == V{1,1,11}) return 708615038;
    if (o == 8 && e == 5 && grps == V{3,3,7}) return 930222225;
    if (o == 9 && e == 4 && grps == V{1,1,3,3,5}) return 9408237;
    if (o == 9 && e == 4 && grps == V{1,1,1,3,7}) return 44424808;
    if (o == 9 && e == 4 && grps == V{1,3,3,3,3}) return 491899955;
    if (o == 9 && e == 4 && grps == V{1,1,1,5,5}) return 526916526;
    if (o == 9 && e == 4 && grps == V{1,1,1,1,9}) return 596949668;
    if (o == 10 && e == 3 && grps == V{1,1,1,1,3,3,3}) return 553999321;
    if (o == 10 && e == 3 && grps == V{1,1,1,1,1,1,7}) return 617346575;
    if (o == 10 && e == 3 && grps == V{1,1,1,1,1,3,5}) return 908448408;
    if (o == 8 && e == 6 && grps == V{7,7}) return 423243957;
    if (o == 8 && e == 6 && grps == V{1,13}) return 430766862;
    if (o == 8 && e == 6 && grps == V{5,9}) return 757413171;
    if (o == 8 && e == 6 && grps == V{3,11}) return 759920806;
    if (o == 9 && e == 5 && grps == V{3,3,3,5}) return 45326927;
    if (o == 9 && e == 5 && grps == V{1,3,5,5}) return 103378997;
    if (o == 9 && e == 5 && grps == V{1,3,3,7}) return 161431067;
    if (o == 9 && e == 5 && grps == V{1,1,5,7}) return 219483137;
    if (o == 9 && e == 5 && grps == V{1,1,3,9}) return 335587277;
    if (o == 9 && e == 5 && grps == V{1,1,1,11}) return 567795557;
    if (o == 10 && e == 4 && grps == V{1,1,1,1,3,7}) return 94114807;
    if (o == 10 && e == 4 && grps == V{1,1,1,1,1,9}) return 388043512;
    if (o == 10 && e == 4 && grps == V{1,1,3,3,3,3}) return 800186109;
    if (o == 10 && e == 4 && grps == V{1,1,1,3,3,5}) return 898162344;
    if (o == 10 && e == 4 && grps == V{1,1,1,1,5,5}) return 996138579;
    if (o == 8 && e == 7 && grps == V{15}) return 308249786;
    if (o == 9 && e == 6 && grps == V{1,7,7}) return 22824442;
    if (o == 9 && e == 6 && grps == V{3,5,7}) return 228997925;
    if (o == 9 && e == 6 && grps == V{1,5,9}) return 419737704;
    if (o == 9 && e == 6 && grps == V{1,1,13}) return 595043779;
    if (o == 9 && e == 6 && grps == V{1,3,11}) return 610477483;
    if (o == 9 && e == 6 && grps == V{5,5,5}) return 832084670;
    if (o == 10 && e == 5 && grps == V{1,3,3,3,5}) return 1667961;
    if (o == 10 && e == 5 && grps == V{1,1,3,3,7}) return 36684532;
    if (o == 10 && e == 5 && grps == V{3,3,3,3,3}) return 484159679;
    if (o == 10 && e == 5 && grps == V{1,1,3,5,5}) return 519176250;
    if (o == 10 && e == 5 && grps == V{1,1,1,5,7}) return 554192821;
    if (o == 10 && e == 5 && grps == V{1,1,1,3,9}) return 589209392;
    if (o == 10 && e == 5 && grps == V{1,1,1,1,11}) return 659242534;
    if (o == 9 && e == 7 && grps == V{5,11}) return 398167607;
    if (o == 9 && e == 7 && grps == V{7,9}) return 729829186;
    if (o == 9 && e == 7 && grps == V{3,13}) return 734844456;
    if (o == 9 && e == 7 && grps == V{1,15}) return 739859726;
    if (o == 10 && e == 6 && grps == V{1,1,1,13}) return 58441744;
    if (o == 10 && e == 6 && grps == V{3,3,5,5}) return 303764841;
    if (o == 10 && e == 6 && grps == V{1,5,5,5}) return 361816911;
    if (o == 10 && e == 6 && grps == V{1,3,5,7}) return 419868981;
    if (o == 10 && e == 6 && grps == V{1,1,7,7}) return 535973121;
    if (o == 10 && e == 6 && grps == V{1,1,5,9}) return 594025191;
    if (o == 10 && e == 6 && grps == V{1,1,3,11}) return 768181401;
    if (o == 9 && e == 8 && grps == V{17}) return 409199592;
    if (o == 10 && e == 7 && grps == V{1,7,9}) return 115426666;
    if (o == 10 && e == 7 && grps == V{3,5,9}) return 321600149;
    if (o == 10 && e == 7 && grps == V{1,3,13}) return 496906224;
    if (o == 10 && e == 7 && grps == V{3,3,11}) return 512339928;
    if (o == 10 && e == 7 && grps == V{5,5,7}) return 527773632;
    if (o == 10 && e == 7 && grps == V{1,1,15}) return 878385782;
    if (o == 10 && e == 7 && grps == V{1,5,11}) return 909253190;
    if (o == 10 && e == 7 && grps == V{3,7,7}) return 924686894;
    if (o == 10 && e == 8 && grps == V{9,9}) return 36414408;
    if (o == 10 && e == 8 && grps == V{3,15}) return 43937313;
    if (o == 10 && e == 8 && grps == V{7,11}) return 370583622;
    if (o == 10 && e == 8 && grps == V{5,13}) return 373091257;
    if (o == 10 && e == 8 && grps == V{1,17}) return 383121797;
    if (o == 10 && e == 9 && grps == V{19}) return 773451073;
    if (o == 10 && e == 10 && grps == V{20}) return 892377077;
    return 0;
}

int get_response(int n, V& v, int o, int e) {
    switch (n) {
        case 2:
            return get_response_2(v, o, e);
            break;
        case 4:
            return get_response_4(v, o, e);
            break;
        case 6:
            return get_response_6(v, o, e);
            break;
        case 8:
            return get_response_8(v, o, e);
            break;
        case 10:
            return get_response_10(v, o, e);
            break;
        case 12:
            return get_response_12(v, o, e);
            break;
        case 14:
            return get_response_14(v, o, e);
            break;
        case 16:
            return get_response_16(v, o, e);
            break;
        case 18:
            return get_response_18(v, o, e);
            break;
        case 20:
            return get_response_20(v, o, e);
            break;
        default:
            return 0;
            break;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    for (int ti = 1; ti <= t; ++ti) {
        int n;
        scanf("%d", &n);
        int players_c = 2 * n;
        V initial_input;
        bool present_0 = false;
        bool present_2 = false;
        for (int i = 0; i < players_c; ++i) {
            int x;
            scanf("%d", &x);
            if (x == 0) {
                present_0 = true;
            } else if (x == 2) {
                present_2 = true;
            }
            initial_input.push_back(x);
        }
        V final_input;
        if (present_0 && present_2) {
            printf("0\n");
            continue;
        }
        if (present_2) {
            for (int i = 1; i < players_c; ++i) {
                if (initial_input[i] == 2) {
                    final_input.push_back(0);
                } else {
                    final_input.push_back(1);
                }
            }
            if (initial_input[0] == 2) {
                final_input.push_back(0);
            } else {
                final_input.push_back(1);
            }
        } else {
            final_input = initial_input;
        }

        // HERE 'final_input' ONLY HAS 0s AND 1s

        int odd_1 = 0;
        int even_1 = 0;
        for (int i = 0; i < players_c; ++i) {
            if (final_input[i] == 1) {
                // ZERO-INDEXED
                if (i % 2 == 0) {
                    odd_1++;
                } else {
                    even_1++;
                }
            }
        }

        if (even_1 > odd_1) {
            printf("0\n");
            continue;
        }
        if (even_1 == odd_1) {
            if (even_1 != 0 && even_1 != n) {
                printf("0\n");
                continue;
            }
        }

        const int ans = get_response(players_c, final_input, odd_1, even_1);

        printf("%d\n", ans);
    }
    dbg("test\n");
    return 0;
}