TopCoder Statistics - Problem Statement

Problem Statement

This problem is about ordinary binary search trees (BSTs). Your task is simple: just simulate a sequence of n insertions.

Inserting an element into a BST is simple: Inserting into an empty BST produces a BST with a single node, containing the inserted value. If we already have a nonempty BST, inserting X is done as follows: Search for X in the BST. If you find it, do nothing. If you don't find it, create a new node containing X and attach it as a leaf to the existing BST in the only valid way.

For example, if we start with an empty BST and insert the values { 40, 20, 60, 70, 80, 30, 10, 30, 90 } in this order, we will get the following tree:

            40
           /  \ 
         20    60
        /  \     \
      10    30    70
                    \
                     80
                       \
                        90

The depth of a node is defined as 1 plus the depth of its parent, with the depth of the root being 0. Let D(x) denote the depth of the node that contains the number x.

Your task will be to insert the values S(0), S(1), ..., S(n-1) and to return the following checksum: sum( D(S(i)) * 10^(5*i) ) modulo (10^9 + 7).

In order to keep the input size small and to force you to process the elements of S one at a time, the sequence S is defined recursively. You are given a int[] Sprefix with p elements: the values S(0), ..., S(p-1). Each of the following elements of S is computed as follows: S(i) = (a * S(i-p) + D(S(i-1)) + 1) modulo m.

Definition

Class:: SimulateBST
Method:: checksum
Parameters:: int, int[], int, int
Returns:: int
Method signature:: int checksum(int n, int[] Sprefix, int a, int m)
(be sure your method is public)

Constraints

n will be between 1 and 500,000, inclusive.
m will be between 1 and 1,000,000,007, inclusive.
a will be between 0 and m-1, inclusive.
Sprefix will have between 1 and min(200,n) elements, inclusive.
Each element of Sprefix will be between 0 and m-1, inclusive.

Examples

3

{10, 20, 30}

0

100

Returns: 99860

The resulting tree looks as follows: 10 \ 20 \ 30 The inserted values appear in the depths {0, 1, 2}, in this order. Thus, the correct checksum to return is (0 * 10^0 + 1 * 10^5 + 2 * 10^10) modulo 1,000,000,007.
3

{10, 10, 10}

0

100

Returns: 0

The resulting tree looks as follows: 10 The inserted values appear in the depths {0, 0, 0}, in this order. Thus, the correct checksum to return is (0 * 10^0 + 0 * 10^5 + 0 * 10^10) modulo 1,000,000,007.
3

{20, 10, 30}

0

100

Returns: 99930

The resulting tree looks as follows: 20 / \ 10 30 The inserted values appear in the depths {0, 1, 1}, in this order. Thus, the correct checksum to return is (0 * 10^0 + 1 * 10^5 + 1 * 10^10) modulo 1,000,000,007.
9

{40, 20, 60, 70, 80, 30, 10, 30, 90}

0

100

Returns: 461469106

The example shown in the ASCII art drawing in the problem statement.
15

{10, 20, 30}

100

1000000007

Returns: 149719615

The inserted values, in order: 10 20 30 1003 2004 3005 100306 200407 300508 10030609 20040710 30050811 3060905 4070997 5081091.
500000

{0}

0

1000000007

Returns: 817756556
500000

{0,100000,24700000}

0

1000000007

Returns: 333762458
500000

{0,100000,24700000}

1

1000000007

Returns: 779009818
500000

{432643263}

325323532

1000000007

Returns: 447039425
500000

{0,100000,24700000}

1

1000000007

Returns: 779009818
500000

{0,100000,24700000}

2

1000000007

Returns: 276126868
473058

{461908963}

0

1000000007

Returns: 588980129
473058

{461908963}

1

1000000007

Returns: 320783751
473058

{461908963}

594466508

1000000007

Returns: 431014506
479731

{276411073, 550232948, 415062492}

0

1000000007

Returns: 41924317
479731

{276411073, 550232948, 415062492}

1

1000000007

Returns: 288656060
479731

{276411073, 550232948, 415062492}

421352829

1000000007

Returns: 293100804
490341

{853713569}

0

1000000007

Returns: 422358620
490341

{853713569}

1

1000000007

Returns: 712411847
490341

{853713569}

449395965

1000000007

Returns: 54197333
493163

{110011131}

0

1000000007

Returns: 38026187
493163

{110011131}

1

1000000007

Returns: 618401865
493163

{110011131}

672710

1000000007

Returns: 198285516
467288

{777236130, 587001530, 9809442, 985054800}

0

1000000007

Returns: 618536801
467288

{777236130, 587001530, 9809442, 985054800}

1

1000000007

Returns: 586010492
467288

{777236130, 587001530, 9809442, 985054800}

875863264

1000000007

Returns: 80665230
470681

{247011036, 255273357, 561856451, 551852547}

0

1000000007

Returns: 116604746
470681

{247011036, 255273357, 561856451, 551852547}

1

1000000007

Returns: 201978300
470681

{247011036, 255273357, 561856451, 551852547}

385561482

1000000007

Returns: 588807778
478981

{35717065, 602310784}

0

1000000007

Returns: 136673847
478981

{35717065, 602310784}

1

1000000007

Returns: 251796761
478981

{35717065, 602310784}

401759009

1000000007

Returns: 941679785
496971

{645292643, 367127108, 598922922}

0

1000000007

Returns: 885462294
496971

{645292643, 367127108, 598922922}

1

1000000007

Returns: 526840827
496971

{645292643, 367127108, 598922922}

617512217

1000000007

Returns: 20053201
499931

{256215401, 846762737}

0

1000000007

Returns: 998056147
499931

{256215401, 846762737}

1

1000000007

Returns: 783301066
499931

{256215401, 846762737}

902613030

1000000007

Returns: 50179518
497785

{134754154}

0

1000000007

Returns: 391890235
497785

{134754154}

1

1000000007

Returns: 541911863
497785

{134754154}

358552530

1000000007

Returns: 756033976
456419

{621000790, 411864481, 545789166, 579958392, 872936870, 271479000, 104258888, 696652797, 936243973, 946086475, 243694079, 995373586, 750769163, 907983561, 359552046, 234670474, 505764849, 799056097, 118268043, 830082628, 447385546, 649243544, 379083493, 724619612, 936679871, 307431950, 943979838, 829933621, 869690042, 256605994, 868778923, 596212365, 989998540, 280879785, 383264903, 571965507, 607076112, 43067572, 519633099, 335229332, 604235495, 837158197, 424641141, 279434604, 784058147, 557700496, 858579682, 237229314, 651057817, 122337491, 673673332, 903481341, 222357206, 407879373, 521192987, 271805617, 648024763, 994029812, 599194165, 160204725, 476619356, 16310367, 182853533, 587328861, 673404583, 863645037, 817622289, 88879941, 80106251, 285346811, 548934239, 872583032, 668418986, 587191332, 511648895, 840026799, 861002056, 467735815, 392537040, 986210305, 815161857, 35628518, 652610126, 284556008, 965501521, 691803009, 653516178, 555088476, 723820366, 976562440, 506602156, 981853232, 760408746, 685395201, 857357003, 338221218, 890700442}

0

1000000007

Returns: 103944482
456419

{621000790, 411864481, 545789166, 579958392, 872936870, 271479000, 104258888, 696652797, 936243973, 946086475, 243694079, 995373586, 750769163, 907983561, 359552046, 234670474, 505764849, 799056097, 118268043, 830082628, 447385546, 649243544, 379083493, 724619612, 936679871, 307431950, 943979838, 829933621, 869690042, 256605994, 868778923, 596212365, 989998540, 280879785, 383264903, 571965507, 607076112, 43067572, 519633099, 335229332, 604235495, 837158197, 424641141, 279434604, 784058147, 557700496, 858579682, 237229314, 651057817, 122337491, 673673332, 903481341, 222357206, 407879373, 521192987, 271805617, 648024763, 994029812, 599194165, 160204725, 476619356, 16310367, 182853533, 587328861, 673404583, 863645037, 817622289, 88879941, 80106251, 285346811, 548934239, 872583032, 668418986, 587191332, 511648895, 840026799, 861002056, 467735815, 392537040, 986210305, 815161857, 35628518, 652610126, 284556008, 965501521, 691803009, 653516178, 555088476, 723820366, 976562440, 506602156, 981853232, 760408746, 685395201, 857357003, 338221218, 890700442}

1

1000000007

Returns: 527432133
456419

{621000790, 411864481, 545789166, 579958392, 872936870, 271479000, 104258888, 696652797, 936243973, 946086475, 243694079, 995373586, 750769163, 907983561, 359552046, 234670474, 505764849, 799056097, 118268043, 830082628, 447385546, 649243544, 379083493, 724619612, 936679871, 307431950, 943979838, 829933621, 869690042, 256605994, 868778923, 596212365, 989998540, 280879785, 383264903, 571965507, 607076112, 43067572, 519633099, 335229332, 604235495, 837158197, 424641141, 279434604, 784058147, 557700496, 858579682, 237229314, 651057817, 122337491, 673673332, 903481341, 222357206, 407879373, 521192987, 271805617, 648024763, 994029812, 599194165, 160204725, 476619356, 16310367, 182853533, 587328861, 673404583, 863645037, 817622289, 88879941, 80106251, 285346811, 548934239, 872583032, 668418986, 587191332, 511648895, 840026799, 861002056, 467735815, 392537040, 986210305, 815161857, 35628518, 652610126, 284556008, 965501521, 691803009, 653516178, 555088476, 723820366, 976562440, 506602156, 981853232, 760408746, 685395201, 857357003, 338221218, 890700442}

23872916

1000000007

Returns: 497260298
487809

{226951148, 371476397, 463467161, 930735750, 742802513, 197585684, 189705944, 504436336, 988878479, 213327221, 137306116, 105675226, 146737412, 784281966, 842998321, 611626153, 369426272, 566292666, 421294032, 116055547, 286544298, 476656188, 485223, 700751158, 131400022, 444604326, 72117357, 396477633, 22249658, 283733899, 44780631, 150794607, 194539708, 793651122, 549388645, 897188377, 527189263, 215981477, 840829695, 829866348, 871544936, 531174522, 567230838, 487039672, 605166843, 609173462, 10723827, 746288199, 79290910, 188036108, 897404346, 161670309, 989836379, 583518861, 363292614, 682389688, 931030468, 50128420, 942251502, 667919250, 251793813, 764765051, 65750734, 406657323, 132229151, 23852118, 95121428}

0

1000000007

Returns: 556446173
487809

{226951148, 371476397, 463467161, 930735750, 742802513, 197585684, 189705944, 504436336, 988878479, 213327221, 137306116, 105675226, 146737412, 784281966, 842998321, 611626153, 369426272, 566292666, 421294032, 116055547, 286544298, 476656188, 485223, 700751158, 131400022, 444604326, 72117357, 396477633, 22249658, 283733899, 44780631, 150794607, 194539708, 793651122, 549388645, 897188377, 527189263, 215981477, 840829695, 829866348, 871544936, 531174522, 567230838, 487039672, 605166843, 609173462, 10723827, 746288199, 79290910, 188036108, 897404346, 161670309, 989836379, 583518861, 363292614, 682389688, 931030468, 50128420, 942251502, 667919250, 251793813, 764765051, 65750734, 406657323, 132229151, 23852118, 95121428}

1

1000000007

Returns: 448701207
487809

{226951148, 371476397, 463467161, 930735750, 742802513, 197585684, 189705944, 504436336, 988878479, 213327221, 137306116, 105675226, 146737412, 784281966, 842998321, 611626153, 369426272, 566292666, 421294032, 116055547, 286544298, 476656188, 485223, 700751158, 131400022, 444604326, 72117357, 396477633, 22249658, 283733899, 44780631, 150794607, 194539708, 793651122, 549388645, 897188377, 527189263, 215981477, 840829695, 829866348, 871544936, 531174522, 567230838, 487039672, 605166843, 609173462, 10723827, 746288199, 79290910, 188036108, 897404346, 161670309, 989836379, 583518861, 363292614, 682389688, 931030468, 50128420, 942251502, 667919250, 251793813, 764765051, 65750734, 406657323, 132229151, 23852118, 95121428}

325052046

1000000007

Returns: 654670522
453531

{330353341, 256750958, 657829698, 962589203, 788143801, 574330895, 162354904, 590480970, 622510786, 818650486, 293303963, 664632564, 921594081, 612929097, 86654360, 604472707, 527479943, 367988208, 597560671, 56030499, 123045707, 443968465, 448443766, 379828288, 973463063, 325142223, 605934918, 906551299, 815748422, 525333703, 641733357, 149950278, 68221557, 545326953, 125699083, 969905990, 495279163, 701102584, 844881430, 487227965, 884403724, 19196099, 466629860, 869380778, 605515027, 560627570, 819709817, 71072587, 839253913, 847423726, 308839297, 841539667, 756726466, 526350671, 539442012, 122544572, 810623578, 263195265, 378160092, 854968508, 355526281, 179226442, 496671190, 24260175, 631062846, 105426212, 720412488, 493352292, 494488687, 297197665, 685081509, 585103878, 736604806, 746550455, 739996155, 986463310, 25537871, 601508804, 203243637, 884873256, 729714784, 308222626, 43901203, 828718827, 282674977, 582239740, 518276962, 411998379, 73514838, 775694911, 843957081, 117075129, 944031161, 559272524, 761348627, 633503745, 643082351, 512516892, 576767593, 799221060, 849100512, 388654383, 621118347, 334682124, 442484489, 826768666, 733157853, 962200196, 964545183, 219977310, 786368716, 679160796, 98188879, 110252490, 550176498, 868789569, 327488403, 434950847, 357293695, 578737879, 897908491, 386678572, 913854417, 116822057, 876386673, 100051728, 917869312, 668324192, 798837166, 457550043, 387115369, 53950146, 375574708, 625812828, 928943728, 60640904, 993976201, 420753700, 680685373, 866619587, 287670031, 273090581, 226141678, 311090680, 224634685}

0

1000000007

Returns: 978909442
453531

{330353341, 256750958, 657829698, 962589203, 788143801, 574330895, 162354904, 590480970, 622510786, 818650486, 293303963, 664632564, 921594081, 612929097, 86654360, 604472707, 527479943, 367988208, 597560671, 56030499, 123045707, 443968465, 448443766, 379828288, 973463063, 325142223, 605934918, 906551299, 815748422, 525333703, 641733357, 149950278, 68221557, 545326953, 125699083, 969905990, 495279163, 701102584, 844881430, 487227965, 884403724, 19196099, 466629860, 869380778, 605515027, 560627570, 819709817, 71072587, 839253913, 847423726, 308839297, 841539667, 756726466, 526350671, 539442012, 122544572, 810623578, 263195265, 378160092, 854968508, 355526281, 179226442, 496671190, 24260175, 631062846, 105426212, 720412488, 493352292, 494488687, 297197665, 685081509, 585103878, 736604806, 746550455, 739996155, 986463310, 25537871, 601508804, 203243637, 884873256, 729714784, 308222626, 43901203, 828718827, 282674977, 582239740, 518276962, 411998379, 73514838, 775694911, 843957081, 117075129, 944031161, 559272524, 761348627, 633503745, 643082351, 512516892, 576767593, 799221060, 849100512, 388654383, 621118347, 334682124, 442484489, 826768666, 733157853, 962200196, 964545183, 219977310, 786368716, 679160796, 98188879, 110252490, 550176498, 868789569, 327488403, 434950847, 357293695, 578737879, 897908491, 386678572, 913854417, 116822057, 876386673, 100051728, 917869312, 668324192, 798837166, 457550043, 387115369, 53950146, 375574708, 625812828, 928943728, 60640904, 993976201, 420753700, 680685373, 866619587, 287670031, 273090581, 226141678, 311090680, 224634685}

1

1000000007

Returns: 29010392
453531

{330353341, 256750958, 657829698, 962589203, 788143801, 574330895, 162354904, 590480970, 622510786, 818650486, 293303963, 664632564, 921594081, 612929097, 86654360, 604472707, 527479943, 367988208, 597560671, 56030499, 123045707, 443968465, 448443766, 379828288, 973463063, 325142223, 605934918, 906551299, 815748422, 525333703, 641733357, 149950278, 68221557, 545326953, 125699083, 969905990, 495279163, 701102584, 844881430, 487227965, 884403724, 19196099, 466629860, 869380778, 605515027, 560627570, 819709817, 71072587, 839253913, 847423726, 308839297, 841539667, 756726466, 526350671, 539442012, 122544572, 810623578, 263195265, 378160092, 854968508, 355526281, 179226442, 496671190, 24260175, 631062846, 105426212, 720412488, 493352292, 494488687, 297197665, 685081509, 585103878, 736604806, 746550455, 739996155, 986463310, 25537871, 601508804, 203243637, 884873256, 729714784, 308222626, 43901203, 828718827, 282674977, 582239740, 518276962, 411998379, 73514838, 775694911, 843957081, 117075129, 944031161, 559272524, 761348627, 633503745, 643082351, 512516892, 576767593, 799221060, 849100512, 388654383, 621118347, 334682124, 442484489, 826768666, 733157853, 962200196, 964545183, 219977310, 786368716, 679160796, 98188879, 110252490, 550176498, 868789569, 327488403, 434950847, 357293695, 578737879, 897908491, 386678572, 913854417, 116822057, 876386673, 100051728, 917869312, 668324192, 798837166, 457550043, 387115369, 53950146, 375574708, 625812828, 928943728, 60640904, 993976201, 420753700, 680685373, 866619587, 287670031, 273090581, 226141678, 311090680, 224634685}

499291496

1000000007

Returns: 146125743
493340

{478078314, 832904610, 472931687, 340861581, 928574706, 724232338, 58810011, 166727022, 623077931, 515073838, 660746, 29553320, 453916726, 930045747, 491132366, 558585770, 470167904, 659341082, 874709996, 923298130, 276727007, 315638992, 110066395, 325424349, 132981064, 182265406, 454286950, 361481930, 534217596, 457410644, 251800944, 540473952, 612320496, 551082069, 282502846, 336070116, 595702143, 24768466, 986216349, 653790074, 722703644, 937805117, 407292477, 918944507, 981459236, 638457511, 632758912, 748166164, 638705883, 740721136, 670024913, 985149561, 495881981, 662478751, 599484617, 192736949, 732861406, 753657890, 404816052, 874553094, 45952094, 195028227, 658188387, 997624442, 194843137, 669887201, 83679517, 520715735, 441328632, 64715109, 240968959, 495771283, 188882615, 999267553, 642031201, 427234463, 4793407, 670493112, 149346959, 798054733, 78153605}

0

1000000007

Returns: 6263031
493340

{478078314, 832904610, 472931687, 340861581, 928574706, 724232338, 58810011, 166727022, 623077931, 515073838, 660746, 29553320, 453916726, 930045747, 491132366, 558585770, 470167904, 659341082, 874709996, 923298130, 276727007, 315638992, 110066395, 325424349, 132981064, 182265406, 454286950, 361481930, 534217596, 457410644, 251800944, 540473952, 612320496, 551082069, 282502846, 336070116, 595702143, 24768466, 986216349, 653790074, 722703644, 937805117, 407292477, 918944507, 981459236, 638457511, 632758912, 748166164, 638705883, 740721136, 670024913, 985149561, 495881981, 662478751, 599484617, 192736949, 732861406, 753657890, 404816052, 874553094, 45952094, 195028227, 658188387, 997624442, 194843137, 669887201, 83679517, 520715735, 441328632, 64715109, 240968959, 495771283, 188882615, 999267553, 642031201, 427234463, 4793407, 670493112, 149346959, 798054733, 78153605}

1

1000000007

Returns: 673903389
493340

{478078314, 832904610, 472931687, 340861581, 928574706, 724232338, 58810011, 166727022, 623077931, 515073838, 660746, 29553320, 453916726, 930045747, 491132366, 558585770, 470167904, 659341082, 874709996, 923298130, 276727007, 315638992, 110066395, 325424349, 132981064, 182265406, 454286950, 361481930, 534217596, 457410644, 251800944, 540473952, 612320496, 551082069, 282502846, 336070116, 595702143, 24768466, 986216349, 653790074, 722703644, 937805117, 407292477, 918944507, 981459236, 638457511, 632758912, 748166164, 638705883, 740721136, 670024913, 985149561, 495881981, 662478751, 599484617, 192736949, 732861406, 753657890, 404816052, 874553094, 45952094, 195028227, 658188387, 997624442, 194843137, 669887201, 83679517, 520715735, 441328632, 64715109, 240968959, 495771283, 188882615, 999267553, 642031201, 427234463, 4793407, 670493112, 149346959, 798054733, 78153605}

601501273

1000000007

Returns: 542988326
475500

{412713771, 536148941, 796563254, 488685466, 676216947}

0

1000000007

Returns: 278628546
475500

{412713771, 536148941, 796563254, 488685466, 676216947}

1

1000000007

Returns: 469272923
475500

{412713771, 536148941, 796563254, 488685466, 676216947}

400720812

1000000007

Returns: 156568890
497882

{548947955, 430015013, 109637006, 92381310, 847718052, 451283482, 442330296, 955753427, 591098775, 111951379, 914736690, 662807300, 187723307, 970209759, 714165864, 535330823, 510886848, 471638318, 640306370, 889758904, 100636318, 424668443, 563196276, 542924252, 351539983, 464477858, 804158884, 980750910, 211144144, 339716496, 426400948, 910274885, 80090326, 142284813, 765291445, 523577852}

0

1000000007

Returns: 460997366
497882

{548947955, 430015013, 109637006, 92381310, 847718052, 451283482, 442330296, 955753427, 591098775, 111951379, 914736690, 662807300, 187723307, 970209759, 714165864, 535330823, 510886848, 471638318, 640306370, 889758904, 100636318, 424668443, 563196276, 542924252, 351539983, 464477858, 804158884, 980750910, 211144144, 339716496, 426400948, 910274885, 80090326, 142284813, 765291445, 523577852}

1

1000000007

Returns: 471254531
497882

{548947955, 430015013, 109637006, 92381310, 847718052, 451283482, 442330296, 955753427, 591098775, 111951379, 914736690, 662807300, 187723307, 970209759, 714165864, 535330823, 510886848, 471638318, 640306370, 889758904, 100636318, 424668443, 563196276, 542924252, 351539983, 464477858, 804158884, 980750910, 211144144, 339716496, 426400948, 910274885, 80090326, 142284813, 765291445, 523577852}

357621018

1000000007

Returns: 883622532
492594

{112574389, 271115611, 521260085, 849335196, 99546047, 383493614, 31925668, 423641319, 670770887, 87319693, 645911309, 240774617, 553833415, 691563364, 226325723, 545243635, 276680942, 765865031, 921223553, 820193932, 329181419, 536941528, 650205373, 122125671, 980661601, 603609901, 67053696, 308060349, 772702299, 190339681, 524279703, 746861204, 259106281, 434185122, 655650968, 509022207, 7600386, 632549435, 937244480, 429046081, 653966169, 252599354, 671430481, 595262024, 401686912, 860241463, 845548682, 114584279, 362763678, 69033214, 168657967, 633379555, 113697937, 256607956, 906858947, 929270383, 196738984, 85869072, 152165059, 552954730, 180549570, 771786201, 177607406, 82929219, 99524446, 135237798, 632552639, 422823419, 925852342, 373997695, 130776087, 445245040, 316619487, 589756569, 687771007, 235734230, 729166753, 985501755, 372498812, 825313015, 96744363, 688723784, 337321499, 109430393, 38425210, 216705223, 870864911, 600314219, 145461625, 354557570, 97596117, 895195765, 342876693, 825430080, 768153274, 712314465, 983564784, 460599972, 543549149, 586221488, 614802102, 808423217, 826572987, 730206253, 967125742, 378121270, 856303625, 559767407, 557787926, 456876900, 684887938, 471503640, 468195242, 726055962, 443577392, 781439377, 526842172, 24347361, 209179998, 350506113, 52690485, 643888823, 460126676, 967702369, 108567928, 471473318, 830378227, 625779005, 133179045, 103394234, 909045810, 359343819, 469391980, 793256113, 978451960, 63364009, 358312655, 845870445, 810271073, 201299071, 981305305, 873194536, 718205950, 438917892, 503374292, 796111176, 981912402, 994070996, 556148090, 510014715, 743845156, 554500238, 128335516, 990286838, 246358736, 213253709, 673613713, 28325499, 579735865, 529972178, 349194489, 988023003, 152479609, 725197699, 175900271, 831185720, 310391575, 77943946, 50425260, 801636735, 899480440}

0

1000000007

Returns: 723582103
492594

{112574389, 271115611, 521260085, 849335196, 99546047, 383493614, 31925668, 423641319, 670770887, 87319693, 645911309, 240774617, 553833415, 691563364, 226325723, 545243635, 276680942, 765865031, 921223553, 820193932, 329181419, 536941528, 650205373, 122125671, 980661601, 603609901, 67053696, 308060349, 772702299, 190339681, 524279703, 746861204, 259106281, 434185122, 655650968, 509022207, 7600386, 632549435, 937244480, 429046081, 653966169, 252599354, 671430481, 595262024, 401686912, 860241463, 845548682, 114584279, 362763678, 69033214, 168657967, 633379555, 113697937, 256607956, 906858947, 929270383, 196738984, 85869072, 152165059, 552954730, 180549570, 771786201, 177607406, 82929219, 99524446, 135237798, 632552639, 422823419, 925852342, 373997695, 130776087, 445245040, 316619487, 589756569, 687771007, 235734230, 729166753, 985501755, 372498812, 825313015, 96744363, 688723784, 337321499, 109430393, 38425210, 216705223, 870864911, 600314219, 145461625, 354557570, 97596117, 895195765, 342876693, 825430080, 768153274, 712314465, 983564784, 460599972, 543549149, 586221488, 614802102, 808423217, 826572987, 730206253, 967125742, 378121270, 856303625, 559767407, 557787926, 456876900, 684887938, 471503640, 468195242, 726055962, 443577392, 781439377, 526842172, 24347361, 209179998, 350506113, 52690485, 643888823, 460126676, 967702369, 108567928, 471473318, 830378227, 625779005, 133179045, 103394234, 909045810, 359343819, 469391980, 793256113, 978451960, 63364009, 358312655, 845870445, 810271073, 201299071, 981305305, 873194536, 718205950, 438917892, 503374292, 796111176, 981912402, 994070996, 556148090, 510014715, 743845156, 554500238, 128335516, 990286838, 246358736, 213253709, 673613713, 28325499, 579735865, 529972178, 349194489, 988023003, 152479609, 725197699, 175900271, 831185720, 310391575, 77943946, 50425260, 801636735, 899480440}

1

1000000007

Returns: 416667151
492594

{112574389, 271115611, 521260085, 849335196, 99546047, 383493614, 31925668, 423641319, 670770887, 87319693, 645911309, 240774617, 553833415, 691563364, 226325723, 545243635, 276680942, 765865031, 921223553, 820193932, 329181419, 536941528, 650205373, 122125671, 980661601, 603609901, 67053696, 308060349, 772702299, 190339681, 524279703, 746861204, 259106281, 434185122, 655650968, 509022207, 7600386, 632549435, 937244480, 429046081, 653966169, 252599354, 671430481, 595262024, 401686912, 860241463, 845548682, 114584279, 362763678, 69033214, 168657967, 633379555, 113697937, 256607956, 906858947, 929270383, 196738984, 85869072, 152165059, 552954730, 180549570, 771786201, 177607406, 82929219, 99524446, 135237798, 632552639, 422823419, 925852342, 373997695, 130776087, 445245040, 316619487, 589756569, 687771007, 235734230, 729166753, 985501755, 372498812, 825313015, 96744363, 688723784, 337321499, 109430393, 38425210, 216705223, 870864911, 600314219, 145461625, 354557570, 97596117, 895195765, 342876693, 825430080, 768153274, 712314465, 983564784, 460599972, 543549149, 586221488, 614802102, 808423217, 826572987, 730206253, 967125742, 378121270, 856303625, 559767407, 557787926, 456876900, 684887938, 471503640, 468195242, 726055962, 443577392, 781439377, 526842172, 24347361, 209179998, 350506113, 52690485, 643888823, 460126676, 967702369, 108567928, 471473318, 830378227, 625779005, 133179045, 103394234, 909045810, 359343819, 469391980, 793256113, 978451960, 63364009, 358312655, 845870445, 810271073, 201299071, 981305305, 873194536, 718205950, 438917892, 503374292, 796111176, 981912402, 994070996, 556148090, 510014715, 743845156, 554500238, 128335516, 990286838, 246358736, 213253709, 673613713, 28325499, 579735865, 529972178, 349194489, 988023003, 152479609, 725197699, 175900271, 831185720, 310391575, 77943946, 50425260, 801636735, 899480440}

971454462

1000000007

Returns: 963166765
489625

{47475366, 689268659, 662912312, 915562149, 718682183, 6766887, 275073122, 370083199, 969893482, 206399912, 596475437, 230917733, 396613518, 968584733, 398019723, 143462528, 217322534, 480391204, 661634889, 37085384, 855177131, 796389967, 873907333, 323850329, 647074276, 718894194, 321677090, 452878615, 118965929, 453793776, 905792744, 449159156, 373129315, 812593217, 534486857, 275762577, 48742449, 777448046, 606607706, 774963800, 740287894, 979135681, 526985908, 246665392, 290525281, 435434484, 62786847, 937032331, 25771035, 422104353, 204805745, 822084014, 448078214, 393888244, 558562208, 95257110, 370603160, 775849257, 931345903, 670691068, 951449378, 673872987, 364001622, 473746333, 929842810, 898059514, 72777336, 946139113, 70281718, 508055586, 286480490, 69102455, 174227103, 219823444, 244202171, 997385309, 453224676, 507494474, 851818540, 212013153, 318593834}

0

1000000007

Returns: 959594044
489625

{47475366, 689268659, 662912312, 915562149, 718682183, 6766887, 275073122, 370083199, 969893482, 206399912, 596475437, 230917733, 396613518, 968584733, 398019723, 143462528, 217322534, 480391204, 661634889, 37085384, 855177131, 796389967, 873907333, 323850329, 647074276, 718894194, 321677090, 452878615, 118965929, 453793776, 905792744, 449159156, 373129315, 812593217, 534486857, 275762577, 48742449, 777448046, 606607706, 774963800, 740287894, 979135681, 526985908, 246665392, 290525281, 435434484, 62786847, 937032331, 25771035, 422104353, 204805745, 822084014, 448078214, 393888244, 558562208, 95257110, 370603160, 775849257, 931345903, 670691068, 951449378, 673872987, 364001622, 473746333, 929842810, 898059514, 72777336, 946139113, 70281718, 508055586, 286480490, 69102455, 174227103, 219823444, 244202171, 997385309, 453224676, 507494474, 851818540, 212013153, 318593834}

1

1000000007

Returns: 794985364
489625

{47475366, 689268659, 662912312, 915562149, 718682183, 6766887, 275073122, 370083199, 969893482, 206399912, 596475437, 230917733, 396613518, 968584733, 398019723, 143462528, 217322534, 480391204, 661634889, 37085384, 855177131, 796389967, 873907333, 323850329, 647074276, 718894194, 321677090, 452878615, 118965929, 453793776, 905792744, 449159156, 373129315, 812593217, 534486857, 275762577, 48742449, 777448046, 606607706, 774963800, 740287894, 979135681, 526985908, 246665392, 290525281, 435434484, 62786847, 937032331, 25771035, 422104353, 204805745, 822084014, 448078214, 393888244, 558562208, 95257110, 370603160, 775849257, 931345903, 670691068, 951449378, 673872987, 364001622, 473746333, 929842810, 898059514, 72777336, 946139113, 70281718, 508055586, 286480490, 69102455, 174227103, 219823444, 244202171, 997385309, 453224676, 507494474, 851818540, 212013153, 318593834}

6376817

1000000007

Returns: 372781335
457483

{606036483, 874630388, 12738098, 269623223, 572736011, 228705735, 571556809, 400151437, 505743508, 984038052, 230058198, 356936916, 429995144, 978506403, 41161877, 722638555, 694139976, 629723229, 445302559, 349449636, 870743927, 863679939, 577243635, 370145438, 961133610, 8033522, 117346907, 22072732, 333903229, 850137163, 52171598, 653879906, 234799331, 883625231, 881753329, 906758648, 562896777, 928195198, 657037158, 3608569, 37488411, 936164376, 595556493, 631512666, 52890094, 411722031, 958920515, 819342377, 498256618, 205051663, 96393176, 297700924, 724900465, 998965079, 682705091, 952571937, 424589421, 547838932, 373515540, 40598036, 952049656, 70079751, 326462496, 645788154, 766988591, 334136497, 55868363, 655206220, 984408050, 474324241, 497583523, 436763796, 782245860, 773450369, 357142261, 772540577, 96563432, 271881319, 915834028, 957372742, 451425244, 401042095, 105467295, 760537921, 405221552, 405306409, 189430592, 317497028, 31989628, 32726129, 617521430, 726017513, 619324219, 871948755, 951735767, 205501001, 135272466, 602537865, 239233694, 92667707, 8177953, 454128574, 459168224, 446959522, 759229787, 454231929, 620958489, 787641000, 136988490, 165344299, 830170089, 774867576, 794438709, 796228454, 914960509, 403416923, 578629390, 688684551, 973483087, 494006315, 282008119, 687581714, 886033331, 688680143, 158444827, 80619762, 42543234, 633350052, 259280604, 873094826, 784896455, 631112252, 137725854, 75703654, 974654823, 18824810, 147075427, 131683492, 556736524, 837370284, 136669034, 657283461, 917253376, 313656809, 611977490, 647129739, 945353533, 449164981, 587730180, 800411910, 524059221, 657631083, 916829793, 623784894, 934807899, 25189944, 179749843, 839551594, 864246081}

0

1000000007

Returns: 305996085
457483

{606036483, 874630388, 12738098, 269623223, 572736011, 228705735, 571556809, 400151437, 505743508, 984038052, 230058198, 356936916, 429995144, 978506403, 41161877, 722638555, 694139976, 629723229, 445302559, 349449636, 870743927, 863679939, 577243635, 370145438, 961133610, 8033522, 117346907, 22072732, 333903229, 850137163, 52171598, 653879906, 234799331, 883625231, 881753329, 906758648, 562896777, 928195198, 657037158, 3608569, 37488411, 936164376, 595556493, 631512666, 52890094, 411722031, 958920515, 819342377, 498256618, 205051663, 96393176, 297700924, 724900465, 998965079, 682705091, 952571937, 424589421, 547838932, 373515540, 40598036, 952049656, 70079751, 326462496, 645788154, 766988591, 334136497, 55868363, 655206220, 984408050, 474324241, 497583523, 436763796, 782245860, 773450369, 357142261, 772540577, 96563432, 271881319, 915834028, 957372742, 451425244, 401042095, 105467295, 760537921, 405221552, 405306409, 189430592, 317497028, 31989628, 32726129, 617521430, 726017513, 619324219, 871948755, 951735767, 205501001, 135272466, 602537865, 239233694, 92667707, 8177953, 454128574, 459168224, 446959522, 759229787, 454231929, 620958489, 787641000, 136988490, 165344299, 830170089, 774867576, 794438709, 796228454, 914960509, 403416923, 578629390, 688684551, 973483087, 494006315, 282008119, 687581714, 886033331, 688680143, 158444827, 80619762, 42543234, 633350052, 259280604, 873094826, 784896455, 631112252, 137725854, 75703654, 974654823, 18824810, 147075427, 131683492, 556736524, 837370284, 136669034, 657283461, 917253376, 313656809, 611977490, 647129739, 945353533, 449164981, 587730180, 800411910, 524059221, 657631083, 916829793, 623784894, 934807899, 25189944, 179749843, 839551594, 864246081}

1

1000000007

Returns: 861262434
457483

{606036483, 874630388, 12738098, 269623223, 572736011, 228705735, 571556809, 400151437, 505743508, 984038052, 230058198, 356936916, 429995144, 978506403, 41161877, 722638555, 694139976, 629723229, 445302559, 349449636, 870743927, 863679939, 577243635, 370145438, 961133610, 8033522, 117346907, 22072732, 333903229, 850137163, 52171598, 653879906, 234799331, 883625231, 881753329, 906758648, 562896777, 928195198, 657037158, 3608569, 37488411, 936164376, 595556493, 631512666, 52890094, 411722031, 958920515, 819342377, 498256618, 205051663, 96393176, 297700924, 724900465, 998965079, 682705091, 952571937, 424589421, 547838932, 373515540, 40598036, 952049656, 70079751, 326462496, 645788154, 766988591, 334136497, 55868363, 655206220, 984408050, 474324241, 497583523, 436763796, 782245860, 773450369, 357142261, 772540577, 96563432, 271881319, 915834028, 957372742, 451425244, 401042095, 105467295, 760537921, 405221552, 405306409, 189430592, 317497028, 31989628, 32726129, 617521430, 726017513, 619324219, 871948755, 951735767, 205501001, 135272466, 602537865, 239233694, 92667707, 8177953, 454128574, 459168224, 446959522, 759229787, 454231929, 620958489, 787641000, 136988490, 165344299, 830170089, 774867576, 794438709, 796228454, 914960509, 403416923, 578629390, 688684551, 973483087, 494006315, 282008119, 687581714, 886033331, 688680143, 158444827, 80619762, 42543234, 633350052, 259280604, 873094826, 784896455, 631112252, 137725854, 75703654, 974654823, 18824810, 147075427, 131683492, 556736524, 837370284, 136669034, 657283461, 917253376, 313656809, 611977490, 647129739, 945353533, 449164981, 587730180, 800411910, 524059221, 657631083, 916829793, 623784894, 934807899, 25189944, 179749843, 839551594, 864246081}

641872479

1000000007

Returns: 176466226
485518

{884453279, 680032466, 777589859, 156614937, 998550953, 248279256, 911137234, 125931884, 162686522, 961925421, 975155805, 306166691, 662212723, 520043731, 963663275, 866417028, 698359883, 526189448, 494591081, 884868198, 916902058, 649637067, 332016440, 439933264, 809428128, 994217734, 482871342, 650222602, 197011876, 13736714, 459504530, 868217808, 846173433, 936515003, 523293685, 525742634, 786028983, 438127919, 368811557, 402588821, 596705226, 324151370, 858690323, 963513038, 329960449, 423562100, 893557231, 888805433, 404231797, 38178810, 669734590, 819272128, 565159598, 288540651, 152087734, 501831491, 421315870, 108815604, 897479257, 947036521, 827960312, 708141539, 115582222, 636528825, 36450493, 394889797, 685588141, 881244446, 956590930, 365287554, 712797109, 727704974, 613878494, 806797731, 158368945, 1176794, 279584623, 377143495, 171791451, 666574063, 922606452, 42708358, 855656830, 864537452, 442722984, 516391627, 770084348, 347333594, 158396353, 285257142, 275044379, 355156688, 438888331, 705675087, 119762142, 220653916, 968931231, 718317149, 189624752, 667265336, 944050741, 247513706, 989801274, 302963301, 713258932, 263814769, 494629645, 746759329, 822514784, 566678279, 366068895, 992101254, 167581775, 566868632, 387564734, 119742495, 962856223, 157283768, 989045509, 190822315, 606252558, 993325837, 244278498, 579712236, 907283297, 613552593, 841249330, 566383529, 892819224, 833095611, 344020031, 685975529, 849986754, 686313605, 581779980, 221132852, 849113146, 683837376, 267547179, 43809681, 392440295, 408431882, 963287787, 809727134, 184616433, 526358251, 653678607, 787348666, 967600908, 779413611, 182842244, 994013394, 937637265}

0

1000000007

Returns: 420691234
485518

{884453279, 680032466, 777589859, 156614937, 998550953, 248279256, 911137234, 125931884, 162686522, 961925421, 975155805, 306166691, 662212723, 520043731, 963663275, 866417028, 698359883, 526189448, 494591081, 884868198, 916902058, 649637067, 332016440, 439933264, 809428128, 994217734, 482871342, 650222602, 197011876, 13736714, 459504530, 868217808, 846173433, 936515003, 523293685, 525742634, 786028983, 438127919, 368811557, 402588821, 596705226, 324151370, 858690323, 963513038, 329960449, 423562100, 893557231, 888805433, 404231797, 38178810, 669734590, 819272128, 565159598, 288540651, 152087734, 501831491, 421315870, 108815604, 897479257, 947036521, 827960312, 708141539, 115582222, 636528825, 36450493, 394889797, 685588141, 881244446, 956590930, 365287554, 712797109, 727704974, 613878494, 806797731, 158368945, 1176794, 279584623, 377143495, 171791451, 666574063, 922606452, 42708358, 855656830, 864537452, 442722984, 516391627, 770084348, 347333594, 158396353, 285257142, 275044379, 355156688, 438888331, 705675087, 119762142, 220653916, 968931231, 718317149, 189624752, 667265336, 944050741, 247513706, 989801274, 302963301, 713258932, 263814769, 494629645, 746759329, 822514784, 566678279, 366068895, 992101254, 167581775, 566868632, 387564734, 119742495, 962856223, 157283768, 989045509, 190822315, 606252558, 993325837, 244278498, 579712236, 907283297, 613552593, 841249330, 566383529, 892819224, 833095611, 344020031, 685975529, 849986754, 686313605, 581779980, 221132852, 849113146, 683837376, 267547179, 43809681, 392440295, 408431882, 963287787, 809727134, 184616433, 526358251, 653678607, 787348666, 967600908, 779413611, 182842244, 994013394, 937637265}

1

1000000007

Returns: 207078175
485518

{884453279, 680032466, 777589859, 156614937, 998550953, 248279256, 911137234, 125931884, 162686522, 961925421, 975155805, 306166691, 662212723, 520043731, 963663275, 866417028, 698359883, 526189448, 494591081, 884868198, 916902058, 649637067, 332016440, 439933264, 809428128, 994217734, 482871342, 650222602, 197011876, 13736714, 459504530, 868217808, 846173433, 936515003, 523293685, 525742634, 786028983, 438127919, 368811557, 402588821, 596705226, 324151370, 858690323, 963513038, 329960449, 423562100, 893557231, 888805433, 404231797, 38178810, 669734590, 819272128, 565159598, 288540651, 152087734, 501831491, 421315870, 108815604, 897479257, 947036521, 827960312, 708141539, 115582222, 636528825, 36450493, 394889797, 685588141, 881244446, 956590930, 365287554, 712797109, 727704974, 613878494, 806797731, 158368945, 1176794, 279584623, 377143495, 171791451, 666574063, 922606452, 42708358, 855656830, 864537452, 442722984, 516391627, 770084348, 347333594, 158396353, 285257142, 275044379, 355156688, 438888331, 705675087, 119762142, 220653916, 968931231, 718317149, 189624752, 667265336, 944050741, 247513706, 989801274, 302963301, 713258932, 263814769, 494629645, 746759329, 822514784, 566678279, 366068895, 992101254, 167581775, 566868632, 387564734, 119742495, 962856223, 157283768, 989045509, 190822315, 606252558, 993325837, 244278498, 579712236, 907283297, 613552593, 841249330, 566383529, 892819224, 833095611, 344020031, 685975529, 849986754, 686313605, 581779980, 221132852, 849113146, 683837376, 267547179, 43809681, 392440295, 408431882, 963287787, 809727134, 184616433, 526358251, 653678607, 787348666, 967600908, 779413611, 182842244, 994013394, 937637265}

207557986

1000000007

Returns: 270988465
500000

{0}

0

1

Returns: 0
500000

{0}

0

2

Returns: 617015063
500000

{0}

1

2

Returns: 166931229
500000

{1}

0

2

Returns: 0
500000

{1}

1

2

Returns: 166931229
500000

{1, 0, 1, 1}

0

2

Returns: 100000
500000

{1, 0, 1, 1}

1

2

Returns: 136907283
497721

{175442115, 294508962, 289641235, 40076899, 138974696, 51130265, 74360024, 359181480, 276674521, 401436065, 311124475, 358613390, 111806766, 146938411, 320658012, 209107908, 59587020, 137203805, 296837155, 192040817, 64222371, 201779092, 199847879, 348647870, 286180214, 120788268, 156196168, 134721702, 326740528, 363440489, 375290721, 349290769, 172237389, 305839496, 20577254, 407875320, 331944856, 111378040, 159036229, 239469668, 414887917, 174592282, 404912687, 61320512, 78520997, 317839517, 98286794, 139818782, 184172309, 147097265, 50827106, 158143311, 111669817, 20329279, 410877606, 145250304, 329198627, 349307289, 116532370, 106491122, 366658714, 264327325, 265859382, 41576188, 204949212, 348453061, 12499157, 351328628, 411765936, 318272207, 80478211, 57137680, 225118905, 161596853, 118287435, 222289370, 403245397, 101893050, 46255076, 115005782, 344844086, 340542703, 356753907, 119995583, 294227122, 47930225, 298261179, 225100443, 165921322, 169309442, 200739623, 63750841, 48894164, 371581782, 168720310, 244064401, 113740333, 413136894, 63063079, 350728330, 46515317, 287665541, 356651873, 182892401, 408036498, 304230410, 369878065, 259980656, 426784151, 117537511, 31871209, 171244662, 165575456, 425061938, 392314993, 395461194, 358170977, 424431830, 203469423, 142178421, 411349922, 317776658, 31871346, 40759744, 137471231}

0

432322633

Returns: 704701085
497721

{175442115, 294508962, 289641235, 40076899, 138974696, 51130265, 74360024, 359181480, 276674521, 401436065, 311124475, 358613390, 111806766, 146938411, 320658012, 209107908, 59587020, 137203805, 296837155, 192040817, 64222371, 201779092, 199847879, 348647870, 286180214, 120788268, 156196168, 134721702, 326740528, 363440489, 375290721, 349290769, 172237389, 305839496, 20577254, 407875320, 331944856, 111378040, 159036229, 239469668, 414887917, 174592282, 404912687, 61320512, 78520997, 317839517, 98286794, 139818782, 184172309, 147097265, 50827106, 158143311, 111669817, 20329279, 410877606, 145250304, 329198627, 349307289, 116532370, 106491122, 366658714, 264327325, 265859382, 41576188, 204949212, 348453061, 12499157, 351328628, 411765936, 318272207, 80478211, 57137680, 225118905, 161596853, 118287435, 222289370, 403245397, 101893050, 46255076, 115005782, 344844086, 340542703, 356753907, 119995583, 294227122, 47930225, 298261179, 225100443, 165921322, 169309442, 200739623, 63750841, 48894164, 371581782, 168720310, 244064401, 113740333, 413136894, 63063079, 350728330, 46515317, 287665541, 356651873, 182892401, 408036498, 304230410, 369878065, 259980656, 426784151, 117537511, 31871209, 171244662, 165575456, 425061938, 392314993, 395461194, 358170977, 424431830, 203469423, 142178421, 411349922, 317776658, 31871346, 40759744, 137471231}

1

432322633

Returns: 87150791
497721

{175442115, 294508962, 289641235, 40076899, 138974696, 51130265, 74360024, 359181480, 276674521, 401436065, 311124475, 358613390, 111806766, 146938411, 320658012, 209107908, 59587020, 137203805, 296837155, 192040817, 64222371, 201779092, 199847879, 348647870, 286180214, 120788268, 156196168, 134721702, 326740528, 363440489, 375290721, 349290769, 172237389, 305839496, 20577254, 407875320, 331944856, 111378040, 159036229, 239469668, 414887917, 174592282, 404912687, 61320512, 78520997, 317839517, 98286794, 139818782, 184172309, 147097265, 50827106, 158143311, 111669817, 20329279, 410877606, 145250304, 329198627, 349307289, 116532370, 106491122, 366658714, 264327325, 265859382, 41576188, 204949212, 348453061, 12499157, 351328628, 411765936, 318272207, 80478211, 57137680, 225118905, 161596853, 118287435, 222289370, 403245397, 101893050, 46255076, 115005782, 344844086, 340542703, 356753907, 119995583, 294227122, 47930225, 298261179, 225100443, 165921322, 169309442, 200739623, 63750841, 48894164, 371581782, 168720310, 244064401, 113740333, 413136894, 63063079, 350728330, 46515317, 287665541, 356651873, 182892401, 408036498, 304230410, 369878065, 259980656, 426784151, 117537511, 31871209, 171244662, 165575456, 425061938, 392314993, 395461194, 358170977, 424431830, 203469423, 142178421, 411349922, 317776658, 31871346, 40759744, 137471231}

245470957

432322633

Returns: 556308531
464434

{342001492, 468604458, 267144960}

0

541236529

Returns: 987911954
464434

{342001492, 468604458, 267144960}

1

541236529

Returns: 526532402
464434

{342001492, 468604458, 267144960}

352830665

541236529

Returns: 39077759
491552

{190555653, 203371246, 256920389, 44568548, 31547554, 547139920, 279749952, 316428352, 213199019, 368616926, 600446388, 361553583, 541555155, 186630427, 351951338, 400184362, 198432453, 168785931, 529817935, 81103305, 37782502, 419704490, 498449467, 483244203, 315973312, 100871023, 528621849, 290424728, 358398435, 303088382, 232994097, 459009036, 81042950, 274266982, 410764214, 347421594, 493608953, 313460938, 172951437, 259903771, 195834966, 389412330, 247206990, 331775805, 38944609, 232566755, 508593434, 26472005, 381771396, 9910859, 305358809, 294035915, 593660090, 446459598, 568643729, 253476460, 487591577, 487750166, 56806493, 88814261, 139726159, 432071304, 475924931, 200996813, 266158026, 49291936, 431349811, 485499074, 571418087, 562501966, 107069334, 599028848, 28449513, 584674225, 481412041, 580321032, 521291716, 173139741, 170221973, 255961014, 295934998, 341992746, 207943922, 598352957, 529434123, 546151788, 295000238, 493684037, 274214649, 361862050, 563823125, 125120813, 237141678, 272982210, 242659281, 35096959, 148065548, 262571502, 480929297, 91022361, 348018470, 588010765, 231993629, 347371571, 101020612, 279436854, 556755568, 168658123, 298489061, 387453591, 149811813, 176767639, 84539943, 197845379, 59908794, 546695397, 192797326, 596447180, 110244358, 307193054, 45065366, 344203210, 199147537, 92800141, 482794486, 296132579, 105909350, 320452292, 209762398, 531432208, 154613845, 146306527, 261236477, 578120339, 258206409, 335525630, 275785662, 487871184, 28229430, 331853797, 202396397, 27309548, 462539400, 187131484, 288525763, 522820014, 202610551, 481592793, 13801157, 396785468, 265601509}

0

612460487

Returns: 240214241
491552

{190555653, 203371246, 256920389, 44568548, 31547554, 547139920, 279749952, 316428352, 213199019, 368616926, 600446388, 361553583, 541555155, 186630427, 351951338, 400184362, 198432453, 168785931, 529817935, 81103305, 37782502, 419704490, 498449467, 483244203, 315973312, 100871023, 528621849, 290424728, 358398435, 303088382, 232994097, 459009036, 81042950, 274266982, 410764214, 347421594, 493608953, 313460938, 172951437, 259903771, 195834966, 389412330, 247206990, 331775805, 38944609, 232566755, 508593434, 26472005, 381771396, 9910859, 305358809, 294035915, 593660090, 446459598, 568643729, 253476460, 487591577, 487750166, 56806493, 88814261, 139726159, 432071304, 475924931, 200996813, 266158026, 49291936, 431349811, 485499074, 571418087, 562501966, 107069334, 599028848, 28449513, 584674225, 481412041, 580321032, 521291716, 173139741, 170221973, 255961014, 295934998, 341992746, 207943922, 598352957, 529434123, 546151788, 295000238, 493684037, 274214649, 361862050, 563823125, 125120813, 237141678, 272982210, 242659281, 35096959, 148065548, 262571502, 480929297, 91022361, 348018470, 588010765, 231993629, 347371571, 101020612, 279436854, 556755568, 168658123, 298489061, 387453591, 149811813, 176767639, 84539943, 197845379, 59908794, 546695397, 192797326, 596447180, 110244358, 307193054, 45065366, 344203210, 199147537, 92800141, 482794486, 296132579, 105909350, 320452292, 209762398, 531432208, 154613845, 146306527, 261236477, 578120339, 258206409, 335525630, 275785662, 487871184, 28229430, 331853797, 202396397, 27309548, 462539400, 187131484, 288525763, 522820014, 202610551, 481592793, 13801157, 396785468, 265601509}

1

612460487

Returns: 11435690
491552

{190555653, 203371246, 256920389, 44568548, 31547554, 547139920, 279749952, 316428352, 213199019, 368616926, 600446388, 361553583, 541555155, 186630427, 351951338, 400184362, 198432453, 168785931, 529817935, 81103305, 37782502, 419704490, 498449467, 483244203, 315973312, 100871023, 528621849, 290424728, 358398435, 303088382, 232994097, 459009036, 81042950, 274266982, 410764214, 347421594, 493608953, 313460938, 172951437, 259903771, 195834966, 389412330, 247206990, 331775805, 38944609, 232566755, 508593434, 26472005, 381771396, 9910859, 305358809, 294035915, 593660090, 446459598, 568643729, 253476460, 487591577, 487750166, 56806493, 88814261, 139726159, 432071304, 475924931, 200996813, 266158026, 49291936, 431349811, 485499074, 571418087, 562501966, 107069334, 599028848, 28449513, 584674225, 481412041, 580321032, 521291716, 173139741, 170221973, 255961014, 295934998, 341992746, 207943922, 598352957, 529434123, 546151788, 295000238, 493684037, 274214649, 361862050, 563823125, 125120813, 237141678, 272982210, 242659281, 35096959, 148065548, 262571502, 480929297, 91022361, 348018470, 588010765, 231993629, 347371571, 101020612, 279436854, 556755568, 168658123, 298489061, 387453591, 149811813, 176767639, 84539943, 197845379, 59908794, 546695397, 192797326, 596447180, 110244358, 307193054, 45065366, 344203210, 199147537, 92800141, 482794486, 296132579, 105909350, 320452292, 209762398, 531432208, 154613845, 146306527, 261236477, 578120339, 258206409, 335525630, 275785662, 487871184, 28229430, 331853797, 202396397, 27309548, 462539400, 187131484, 288525763, 522820014, 202610551, 481592793, 13801157, 396785468, 265601509}

431034017

612460487

Returns: 533153876
461735

{53886781, 231001523, 338394543, 432279362, 322000707, 287368544, 99681987, 325095825, 247043053, 46682255, 506017811, 328610375, 253339595, 317597696, 490139238, 192337769, 189849489, 325087308, 494085229, 310477149, 312925620, 55600562, 329287801, 40733571, 73633916, 429162252, 543472064, 456325863, 157158293, 406337811, 412934040, 240725785, 444055918, 477778426, 195851681, 271125097, 430168720, 343942783, 359893798, 133832752, 405968573, 467516742, 150919523, 96397850, 465623791, 268026355, 253058919, 3795734, 275981015, 27255389}

0

544656692

Returns: 803790534
461735

{53886781, 231001523, 338394543, 432279362, 322000707, 287368544, 99681987, 325095825, 247043053, 46682255, 506017811, 328610375, 253339595, 317597696, 490139238, 192337769, 189849489, 325087308, 494085229, 310477149, 312925620, 55600562, 329287801, 40733571, 73633916, 429162252, 543472064, 456325863, 157158293, 406337811, 412934040, 240725785, 444055918, 477778426, 195851681, 271125097, 430168720, 343942783, 359893798, 133832752, 405968573, 467516742, 150919523, 96397850, 465623791, 268026355, 253058919, 3795734, 275981015, 27255389}

1

544656692

Returns: 680631231
461735

{53886781, 231001523, 338394543, 432279362, 322000707, 287368544, 99681987, 325095825, 247043053, 46682255, 506017811, 328610375, 253339595, 317597696, 490139238, 192337769, 189849489, 325087308, 494085229, 310477149, 312925620, 55600562, 329287801, 40733571, 73633916, 429162252, 543472064, 456325863, 157158293, 406337811, 412934040, 240725785, 444055918, 477778426, 195851681, 271125097, 430168720, 343942783, 359893798, 133832752, 405968573, 467516742, 150919523, 96397850, 465623791, 268026355, 253058919, 3795734, 275981015, 27255389}

361917828

544656692

Returns: 575630288
484827

{136148695, 36330789}

0

425869261

Returns: 815003818
484827

{136148695, 36330789}

1

425869261

Returns: 742468054
484827

{136148695, 36330789}

364353052

425869261

Returns: 718625104
465919

{23661510, 23237321, 5610005, 45930297, 33499580, 17508413, 18831203, 51596737, 40099560, 24696558, 13715168, 3217880, 17478180, 32698440, 15621629, 44594728, 7339037, 35443456, 20512674, 12387031, 26627934, 18869283, 49700813, 39710469, 47836784, 13530432, 35436703, 18808217, 50995624, 10767247, 10834516, 21481765, 10283385, 18671564, 32351856, 6624490, 19172626, 46581535, 17542585, 10133992, 26242412, 45262118, 14720083, 14884997, 53803070, 50537000, 53008555, 11953050, 5786909, 19466043, 34683921, 9780835, 31214479, 52180774, 19810534, 2118851, 7153065, 45613368, 37239555, 14822484, 13913559, 7133730, 13216541, 33513761, 25719808, 20295782, 48090533, 17135623, 816738, 22509538, 24184348, 28183886, 6488926, 5901698, 22118289, 17452304, 35789948, 15551687, 38991901, 48276831, 46311219, 9243430, 16505168, 45193396, 53773322, 33371150, 36967463, 46846182, 42422199, 13465019, 51808624, 2289269, 49721644, 11254892, 1590543, 38208797, 21054846, 15270130, 46041378, 24614873, 15372733, 16420322, 32791782, 24863229, 13541045, 28499228, 12511546, 31111927, 39966914, 41265856, 14929608, 2386060, 51643170, 27293004, 31281346, 15557983, 28422926, 51382598, 1220176, 28371044, 41487523, 34403354, 4425183, 32924039, 12976601, 26229102, 12584155, 48619701, 138199, 16077832, 33033857, 34883010, 787669, 36945266, 19836230, 32169141, 21088425, 20562173, 41008467, 46972514, 44622104, 34833646, 47609627, 46466464, 50024664, 42065838, 33879543, 25201240, 41923012, 14926858, 45243612, 3615215, 14596978, 14664037, 51148254, 32966452, 39454115, 29597508, 33446038, 26838823, 36493360}

0

54359803

Returns: 342836680
465919

{23661510, 23237321, 5610005, 45930297, 33499580, 17508413, 18831203, 51596737, 40099560, 24696558, 13715168, 3217880, 17478180, 32698440, 15621629, 44594728, 7339037, 35443456, 20512674, 12387031, 26627934, 18869283, 49700813, 39710469, 47836784, 13530432, 35436703, 18808217, 50995624, 10767247, 10834516, 21481765, 10283385, 18671564, 32351856, 6624490, 19172626, 46581535, 17542585, 10133992, 26242412, 45262118, 14720083, 14884997, 53803070, 50537000, 53008555, 11953050, 5786909, 19466043, 34683921, 9780835, 31214479, 52180774, 19810534, 2118851, 7153065, 45613368, 37239555, 14822484, 13913559, 7133730, 13216541, 33513761, 25719808, 20295782, 48090533, 17135623, 816738, 22509538, 24184348, 28183886, 6488926, 5901698, 22118289, 17452304, 35789948, 15551687, 38991901, 48276831, 46311219, 9243430, 16505168, 45193396, 53773322, 33371150, 36967463, 46846182, 42422199, 13465019, 51808624, 2289269, 49721644, 11254892, 1590543, 38208797, 21054846, 15270130, 46041378, 24614873, 15372733, 16420322, 32791782, 24863229, 13541045, 28499228, 12511546, 31111927, 39966914, 41265856, 14929608, 2386060, 51643170, 27293004, 31281346, 15557983, 28422926, 51382598, 1220176, 28371044, 41487523, 34403354, 4425183, 32924039, 12976601, 26229102, 12584155, 48619701, 138199, 16077832, 33033857, 34883010, 787669, 36945266, 19836230, 32169141, 21088425, 20562173, 41008467, 46972514, 44622104, 34833646, 47609627, 46466464, 50024664, 42065838, 33879543, 25201240, 41923012, 14926858, 45243612, 3615215, 14596978, 14664037, 51148254, 32966452, 39454115, 29597508, 33446038, 26838823, 36493360}

1

54359803

Returns: 831364804
465919

{23661510, 23237321, 5610005, 45930297, 33499580, 17508413, 18831203, 51596737, 40099560, 24696558, 13715168, 3217880, 17478180, 32698440, 15621629, 44594728, 7339037, 35443456, 20512674, 12387031, 26627934, 18869283, 49700813, 39710469, 47836784, 13530432, 35436703, 18808217, 50995624, 10767247, 10834516, 21481765, 10283385, 18671564, 32351856, 6624490, 19172626, 46581535, 17542585, 10133992, 26242412, 45262118, 14720083, 14884997, 53803070, 50537000, 53008555, 11953050, 5786909, 19466043, 34683921, 9780835, 31214479, 52180774, 19810534, 2118851, 7153065, 45613368, 37239555, 14822484, 13913559, 7133730, 13216541, 33513761, 25719808, 20295782, 48090533, 17135623, 816738, 22509538, 24184348, 28183886, 6488926, 5901698, 22118289, 17452304, 35789948, 15551687, 38991901, 48276831, 46311219, 9243430, 16505168, 45193396, 53773322, 33371150, 36967463, 46846182, 42422199, 13465019, 51808624, 2289269, 49721644, 11254892, 1590543, 38208797, 21054846, 15270130, 46041378, 24614873, 15372733, 16420322, 32791782, 24863229, 13541045, 28499228, 12511546, 31111927, 39966914, 41265856, 14929608, 2386060, 51643170, 27293004, 31281346, 15557983, 28422926, 51382598, 1220176, 28371044, 41487523, 34403354, 4425183, 32924039, 12976601, 26229102, 12584155, 48619701, 138199, 16077832, 33033857, 34883010, 787669, 36945266, 19836230, 32169141, 21088425, 20562173, 41008467, 46972514, 44622104, 34833646, 47609627, 46466464, 50024664, 42065838, 33879543, 25201240, 41923012, 14926858, 45243612, 3615215, 14596978, 14664037, 51148254, 32966452, 39454115, 29597508, 33446038, 26838823, 36493360}

26987495

54359803

Returns: 940754237
477433

{140704315}

0

150271763

Returns: 79326888
477433

{140704315}

1

150271763

Returns: 990528707
477433

{140704315}

91176945

150271763

Returns: 876439419
498721

{388544002, 547493938, 414265720, 281294714, 164181214, 56688850, 230979638, 56690750, 281029825, 277614973, 189249999, 401874113, 401158250, 248011406, 143127586, 253225509, 113920546, 144266278, 385963700, 55165532, 155823830, 187481095, 418898248, 290524755, 560740181, 67494238, 571590225, 165324553, 258641277, 345948914, 487992591, 556632984, 282034523, 101148590, 376513442, 275478582, 10155154, 299698975, 572832777, 287353556, 499217863, 563220039, 501418462, 161660824, 390297591, 144895586, 223253833, 21160640, 105468699, 58139390, 412762888, 530315118, 221224953, 567823096, 169462444, 394835119, 62328240, 195162645, 255945349, 517031726, 514805273, 458392916, 61241079, 533779298, 251564145, 550377765, 348597778, 547385011, 236234056, 416981367, 489729987, 145735096, 182328204, 184478658, 212721360, 357046587, 2010801, 561926682, 214741079, 480850466, 175644374, 313103870, 560192715, 466535559, 507180463, 468208979, 23044474, 179104229, 459795417, 428283207, 34652972, 53058897, 65053482, 109357599, 222852837, 517651730, 202174619, 34418159, 572991024, 129017748, 17742396, 356236843, 277872449, 514973481, 298763155, 105827682, 125632138, 385260198, 518939842, 9716293, 298988001, 494047372, 478896674, 199322697, 132361033, 277800698, 395851892, 500197733, 57880096, 528282646, 35188299, 457263126, 87950281, 225533883, 398039651, 210635569, 247461793, 153767819, 221121272, 532004561, 551951617, 114532246, 312032389, 580240073, 106770599, 526143480, 208486131, 40580456, 161287836, 543532827, 277548715, 159082738, 301181834, 400523950, 157695078, 357240199, 571040945, 397614256, 136452756, 153953317, 459828809, 436724952, 341034993, 193067737, 402755978, 20344374, 112322228, 455785522, 179101077, 69804500, 108226771, 139419976, 110871231, 82081724, 234031193, 30770936, 194248717, 415231217, 103621867, 68780599, 517035513, 18738801, 131750027, 185586893, 358375197, 140551516, 141293877, 299279181, 240666055, 148905246, 55229543, 416444351, 170467705, 450047870, 31346005, 77974721, 262086705, 541027220, 458114087, 545839915, 67975262, 380272268, 260698435, 382992504, 286030621, 202201186, 47483763, 328120033, 47827540, 190332539}

0

585987427

Returns: 113523753
498721

{388544002, 547493938, 414265720, 281294714, 164181214, 56688850, 230979638, 56690750, 281029825, 277614973, 189249999, 401874113, 401158250, 248011406, 143127586, 253225509, 113920546, 144266278, 385963700, 55165532, 155823830, 187481095, 418898248, 290524755, 560740181, 67494238, 571590225, 165324553, 258641277, 345948914, 487992591, 556632984, 282034523, 101148590, 376513442, 275478582, 10155154, 299698975, 572832777, 287353556, 499217863, 563220039, 501418462, 161660824, 390297591, 144895586, 223253833, 21160640, 105468699, 58139390, 412762888, 530315118, 221224953, 567823096, 169462444, 394835119, 62328240, 195162645, 255945349, 517031726, 514805273, 458392916, 61241079, 533779298, 251564145, 550377765, 348597778, 547385011, 236234056, 416981367, 489729987, 145735096, 182328204, 184478658, 212721360, 357046587, 2010801, 561926682, 214741079, 480850466, 175644374, 313103870, 560192715, 466535559, 507180463, 468208979, 23044474, 179104229, 459795417, 428283207, 34652972, 53058897, 65053482, 109357599, 222852837, 517651730, 202174619, 34418159, 572991024, 129017748, 17742396, 356236843, 277872449, 514973481, 298763155, 105827682, 125632138, 385260198, 518939842, 9716293, 298988001, 494047372, 478896674, 199322697, 132361033, 277800698, 395851892, 500197733, 57880096, 528282646, 35188299, 457263126, 87950281, 225533883, 398039651, 210635569, 247461793, 153767819, 221121272, 532004561, 551951617, 114532246, 312032389, 580240073, 106770599, 526143480, 208486131, 40580456, 161287836, 543532827, 277548715, 159082738, 301181834, 400523950, 157695078, 357240199, 571040945, 397614256, 136452756, 153953317, 459828809, 436724952, 341034993, 193067737, 402755978, 20344374, 112322228, 455785522, 179101077, 69804500, 108226771, 139419976, 110871231, 82081724, 234031193, 30770936, 194248717, 415231217, 103621867, 68780599, 517035513, 18738801, 131750027, 185586893, 358375197, 140551516, 141293877, 299279181, 240666055, 148905246, 55229543, 416444351, 170467705, 450047870, 31346005, 77974721, 262086705, 541027220, 458114087, 545839915, 67975262, 380272268, 260698435, 382992504, 286030621, 202201186, 47483763, 328120033, 47827540, 190332539}

1

585987427

Returns: 558817081
498721

{388544002, 547493938, 414265720, 281294714, 164181214, 56688850, 230979638, 56690750, 281029825, 277614973, 189249999, 401874113, 401158250, 248011406, 143127586, 253225509, 113920546, 144266278, 385963700, 55165532, 155823830, 187481095, 418898248, 290524755, 560740181, 67494238, 571590225, 165324553, 258641277, 345948914, 487992591, 556632984, 282034523, 101148590, 376513442, 275478582, 10155154, 299698975, 572832777, 287353556, 499217863, 563220039, 501418462, 161660824, 390297591, 144895586, 223253833, 21160640, 105468699, 58139390, 412762888, 530315118, 221224953, 567823096, 169462444, 394835119, 62328240, 195162645, 255945349, 517031726, 514805273, 458392916, 61241079, 533779298, 251564145, 550377765, 348597778, 547385011, 236234056, 416981367, 489729987, 145735096, 182328204, 184478658, 212721360, 357046587, 2010801, 561926682, 214741079, 480850466, 175644374, 313103870, 560192715, 466535559, 507180463, 468208979, 23044474, 179104229, 459795417, 428283207, 34652972, 53058897, 65053482, 109357599, 222852837, 517651730, 202174619, 34418159, 572991024, 129017748, 17742396, 356236843, 277872449, 514973481, 298763155, 105827682, 125632138, 385260198, 518939842, 9716293, 298988001, 494047372, 478896674, 199322697, 132361033, 277800698, 395851892, 500197733, 57880096, 528282646, 35188299, 457263126, 87950281, 225533883, 398039651, 210635569, 247461793, 153767819, 221121272, 532004561, 551951617, 114532246, 312032389, 580240073, 106770599, 526143480, 208486131, 40580456, 161287836, 543532827, 277548715, 159082738, 301181834, 400523950, 157695078, 357240199, 571040945, 397614256, 136452756, 153953317, 459828809, 436724952, 341034993, 193067737, 402755978, 20344374, 112322228, 455785522, 179101077, 69804500, 108226771, 139419976, 110871231, 82081724, 234031193, 30770936, 194248717, 415231217, 103621867, 68780599, 517035513, 18738801, 131750027, 185586893, 358375197, 140551516, 141293877, 299279181, 240666055, 148905246, 55229543, 416444351, 170467705, 450047870, 31346005, 77974721, 262086705, 541027220, 458114087, 545839915, 67975262, 380272268, 260698435, 382992504, 286030621, 202201186, 47483763, 328120033, 47827540, 190332539}

63516253

585987427

Returns: 16171290
470399

{365330557, 50577083, 394685689, 270204400}

0

562056356

Returns: 496909022
470399

{365330557, 50577083, 394685689, 270204400}

1

562056356

Returns: 258831163
470399

{365330557, 50577083, 394685689, 270204400}

196558363

562056356

Returns: 387990299
491133

{25891435, 500003984, 246945115, 278753557, 448365805, 515588645, 5752703, 56076456, 366298956, 436999491, 99641421, 81435418, 367121133, 224108135, 278851271, 367238887, 129607545, 163207890, 483867094, 406535781, 360740995, 217129347, 276786381, 294585479, 491354121, 268399389, 517757549, 190466591, 439481772, 417095665, 212910190, 37795998, 347434840, 47746916, 252600135, 72385970, 125070530, 293970753, 257113855, 517674450, 473753261, 150119021, 103078065, 8879673, 357689261, 304566467, 42998395, 284345844, 401900570, 400092316, 391982934, 169679834, 94422491}

0

558633718

Returns: 799710595
491133

{25891435, 500003984, 246945115, 278753557, 448365805, 515588645, 5752703, 56076456, 366298956, 436999491, 99641421, 81435418, 367121133, 224108135, 278851271, 367238887, 129607545, 163207890, 483867094, 406535781, 360740995, 217129347, 276786381, 294585479, 491354121, 268399389, 517757549, 190466591, 439481772, 417095665, 212910190, 37795998, 347434840, 47746916, 252600135, 72385970, 125070530, 293970753, 257113855, 517674450, 473753261, 150119021, 103078065, 8879673, 357689261, 304566467, 42998395, 284345844, 401900570, 400092316, 391982934, 169679834, 94422491}

1

558633718

Returns: 813400695
491133

{25891435, 500003984, 246945115, 278753557, 448365805, 515588645, 5752703, 56076456, 366298956, 436999491, 99641421, 81435418, 367121133, 224108135, 278851271, 367238887, 129607545, 163207890, 483867094, 406535781, 360740995, 217129347, 276786381, 294585479, 491354121, 268399389, 517757549, 190466591, 439481772, 417095665, 212910190, 37795998, 347434840, 47746916, 252600135, 72385970, 125070530, 293970753, 257113855, 517674450, 473753261, 150119021, 103078065, 8879673, 357689261, 304566467, 42998395, 284345844, 401900570, 400092316, 391982934, 169679834, 94422491}

276033387

558633718

Returns: 290658098
481620

{81253658, 51955469, 21863103}

0

96455717

Returns: 841906877
481620

{81253658, 51955469, 21863103}

1

96455717

Returns: 367211552
481620

{81253658, 51955469, 21863103}

39597985

96455717

Returns: 415346103
479184

{33445386, 96803380, 32347483}

0

129565823

Returns: 353158344
479184

{33445386, 96803380, 32347483}

1

129565823

Returns: 570939303
479184

{33445386, 96803380, 32347483}

128244891

129565823

Returns: 880734179
499918

{35749791, 821399374, 327454326, 694479045, 450406514, 531153724, 265783814, 227603246, 60560270, 744572697, 292550425, 854161230, 622681490, 624440559, 228344211, 553293429, 41254426, 345312096, 294178269, 143121695, 446931315, 128712614, 124007020, 245111140, 569414851, 192525605, 748334009, 779796208, 655503114, 807563157, 194900250, 647330993, 119513916, 420286676, 347711872, 288080402, 7517714, 740115153, 855855854, 742992524, 537290480, 574456193, 293121693, 773416207, 189880157}

0

868017398

Returns: 593763032
499918

{35749791, 821399374, 327454326, 694479045, 450406514, 531153724, 265783814, 227603246, 60560270, 744572697, 292550425, 854161230, 622681490, 624440559, 228344211, 553293429, 41254426, 345312096, 294178269, 143121695, 446931315, 128712614, 124007020, 245111140, 569414851, 192525605, 748334009, 779796208, 655503114, 807563157, 194900250, 647330993, 119513916, 420286676, 347711872, 288080402, 7517714, 740115153, 855855854, 742992524, 537290480, 574456193, 293121693, 773416207, 189880157}

1

868017398

Returns: 735939764
499918

{35749791, 821399374, 327454326, 694479045, 450406514, 531153724, 265783814, 227603246, 60560270, 744572697, 292550425, 854161230, 622681490, 624440559, 228344211, 553293429, 41254426, 345312096, 294178269, 143121695, 446931315, 128712614, 124007020, 245111140, 569414851, 192525605, 748334009, 779796208, 655503114, 807563157, 194900250, 647330993, 119513916, 420286676, 347711872, 288080402, 7517714, 740115153, 855855854, 742992524, 537290480, 574456193, 293121693, 773416207, 189880157}

547861489

868017398

Returns: 436681236
450560

{720848160, 439916696, 618354816}

0

922298490

Returns: 439668341
450560

{720848160, 439916696, 618354816}

1

922298490

Returns: 222966612
450560

{720848160, 439916696, 618354816}

626808372

922298490

Returns: 493301146
471667

{114877744, 365482263, 370537365, 180858466, 216566311, 375179916, 199670267, 367763712, 396915160, 113607330, 73407686, 190516533, 275906509, 15562659, 249248559, 79531149, 293101995, 188876839, 212417739, 48025103, 46201256, 39574615, 298032339, 225309436, 270735795, 82738107, 359414700, 99431862, 90383498, 243231407, 37213394, 114658810, 196735261, 362226482, 205546705, 103377919, 267180200, 375931252, 37840089, 337146910, 299328640, 266569157, 106576786, 30169195, 10753087, 173482376, 301802303, 104490458, 204332395, 6809635, 74390096, 298542732, 359895456, 211009026, 197425311, 124506447, 58408036, 134138391, 107135790, 207602584, 138339416, 316262512, 247477409, 392048221, 212737652, 226006784, 259677015, 18528001, 89004726, 83308893, 104035413, 190782851, 319869425, 387952862, 285760166, 188352903, 79199416}

0

402208312

Returns: 998476578
471667

{114877744, 365482263, 370537365, 180858466, 216566311, 375179916, 199670267, 367763712, 396915160, 113607330, 73407686, 190516533, 275906509, 15562659, 249248559, 79531149, 293101995, 188876839, 212417739, 48025103, 46201256, 39574615, 298032339, 225309436, 270735795, 82738107, 359414700, 99431862, 90383498, 243231407, 37213394, 114658810, 196735261, 362226482, 205546705, 103377919, 267180200, 375931252, 37840089, 337146910, 299328640, 266569157, 106576786, 30169195, 10753087, 173482376, 301802303, 104490458, 204332395, 6809635, 74390096, 298542732, 359895456, 211009026, 197425311, 124506447, 58408036, 134138391, 107135790, 207602584, 138339416, 316262512, 247477409, 392048221, 212737652, 226006784, 259677015, 18528001, 89004726, 83308893, 104035413, 190782851, 319869425, 387952862, 285760166, 188352903, 79199416}

1

402208312

Returns: 647980073
471667

{114877744, 365482263, 370537365, 180858466, 216566311, 375179916, 199670267, 367763712, 396915160, 113607330, 73407686, 190516533, 275906509, 15562659, 249248559, 79531149, 293101995, 188876839, 212417739, 48025103, 46201256, 39574615, 298032339, 225309436, 270735795, 82738107, 359414700, 99431862, 90383498, 243231407, 37213394, 114658810, 196735261, 362226482, 205546705, 103377919, 267180200, 375931252, 37840089, 337146910, 299328640, 266569157, 106576786, 30169195, 10753087, 173482376, 301802303, 104490458, 204332395, 6809635, 74390096, 298542732, 359895456, 211009026, 197425311, 124506447, 58408036, 134138391, 107135790, 207602584, 138339416, 316262512, 247477409, 392048221, 212737652, 226006784, 259677015, 18528001, 89004726, 83308893, 104035413, 190782851, 319869425, 387952862, 285760166, 188352903, 79199416}

372257341

402208312

Returns: 365978213
492327

{42529083, 12345202, 12051061, 3383376, 798106, 46952780, 23977657, 14151458, 1561067, 33972837, 8943750, 2044572, 49053368, 23051120, 50097882, 16974171, 20263038, 27809495, 49868575, 9609270, 30045763, 48570139, 29773979, 10819218, 44546850, 10728427, 35594335, 28615435, 882173, 8622404, 12183864, 33022544, 8502446, 27987894, 24843725, 1682233, 574661}

0

50639983

Returns: 18584699
492327

{42529083, 12345202, 12051061, 3383376, 798106, 46952780, 23977657, 14151458, 1561067, 33972837, 8943750, 2044572, 49053368, 23051120, 50097882, 16974171, 20263038, 27809495, 49868575, 9609270, 30045763, 48570139, 29773979, 10819218, 44546850, 10728427, 35594335, 28615435, 882173, 8622404, 12183864, 33022544, 8502446, 27987894, 24843725, 1682233, 574661}

1

50639983

Returns: 584163372
492327

{42529083, 12345202, 12051061, 3383376, 798106, 46952780, 23977657, 14151458, 1561067, 33972837, 8943750, 2044572, 49053368, 23051120, 50097882, 16974171, 20263038, 27809495, 49868575, 9609270, 30045763, 48570139, 29773979, 10819218, 44546850, 10728427, 35594335, 28615435, 882173, 8622404, 12183864, 33022544, 8502446, 27987894, 24843725, 1682233, 574661}

39057526

50639983

Returns: 769267843
463357

{149875824, 277237820}

0

492634660

Returns: 652993845
463357

{149875824, 277237820}

1

492634660

Returns: 413238066
463357

{149875824, 277237820}

388879753

492634660

Returns: 497151799
470052

{344876993, 108626093}

0

827424775

Returns: 811820348
470052

{344876993, 108626093}

1

827424775

Returns: 986051511
470052

{344876993, 108626093}

628237464

827424775

Returns: 44611321
486272

{113095571, 330802881, 245623480, 238312401, 100497127, 121139193, 350561320, 147596976, 12903922, 338960960, 51398888, 212081701, 25750261, 195598426, 304880784, 339856378, 32940057, 235129065, 20911474, 57069388, 137299534, 183282926, 353738927, 113252580, 197303303, 5417211, 185926697, 119014455, 113414165, 105131117, 99537480, 181264390, 125961610, 208402006, 32177296, 356557854, 62268672, 69365247, 327494899, 272876125, 332925365, 225026439, 175220241, 195203264, 240873685, 260925420, 247804454, 266302441, 318305485, 90830961, 19518346, 223881473, 318279161, 272532742, 293028895, 249450465, 173156132, 198956528, 232567586, 91516482, 279107218, 348299193, 297369606, 286997174, 123097456, 266535784, 220812909, 24924973, 188688280, 163379711, 335156906, 132146892, 251958074, 131325299, 109544837, 49346867, 267694186, 355700831, 202483374, 311730295, 116566920, 267303503, 12670130, 172145278, 133450376, 103956457, 177429986, 392123320, 314878126, 277659730, 120288866, 9345399, 211956280, 380310504, 21792827, 273912171, 312922745, 179494811, 298141203, 291222232, 175636520, 185527172, 339983902, 274282902, 246695540, 335143512, 18772783, 310285967, 319680450, 99133440, 50737806, 111132177, 33920202, 134449523, 309646714, 142876103, 205315390, 314894458, 359119849, 14973877, 52639682, 279742907, 272708691, 368789702, 195192251, 387795092, 224107982, 140069074, 189668896, 143648768, 371354104, 78473037, 266896588, 293631811, 359381412, 339892783, 68383666, 328568778, 328594183, 289179209, 81772250, 166140729, 151823105, 24833777, 325315809, 233587705, 195625838, 293066227, 331236762, 208172879, 378335092, 334874643, 306153299, 338808170, 361524190, 236246373, 296009894, 335400790, 387244233, 448111, 139432856, 152045255, 257751613, 136619307, 301776003, 392041342, 352627528, 206670493, 85343055, 105110019, 212343624, 220083482, 383318653, 343160016, 251644367, 30899823, 157387135, 265891532, 51772453, 280808567, 337362935, 161321516, 382051688, 196496983, 277743265, 297275039, 131970027, 45719208, 310048645, 37603260}

0

395299422

Returns: 976927205
486272

{113095571, 330802881, 245623480, 238312401, 100497127, 121139193, 350561320, 147596976, 12903922, 338960960, 51398888, 212081701, 25750261, 195598426, 304880784, 339856378, 32940057, 235129065, 20911474, 57069388, 137299534, 183282926, 353738927, 113252580, 197303303, 5417211, 185926697, 119014455, 113414165, 105131117, 99537480, 181264390, 125961610, 208402006, 32177296, 356557854, 62268672, 69365247, 327494899, 272876125, 332925365, 225026439, 175220241, 195203264, 240873685, 260925420, 247804454, 266302441, 318305485, 90830961, 19518346, 223881473, 318279161, 272532742, 293028895, 249450465, 173156132, 198956528, 232567586, 91516482, 279107218, 348299193, 297369606, 286997174, 123097456, 266535784, 220812909, 24924973, 188688280, 163379711, 335156906, 132146892, 251958074, 131325299, 109544837, 49346867, 267694186, 355700831, 202483374, 311730295, 116566920, 267303503, 12670130, 172145278, 133450376, 103956457, 177429986, 392123320, 314878126, 277659730, 120288866, 9345399, 211956280, 380310504, 21792827, 273912171, 312922745, 179494811, 298141203, 291222232, 175636520, 185527172, 339983902, 274282902, 246695540, 335143512, 18772783, 310285967, 319680450, 99133440, 50737806, 111132177, 33920202, 134449523, 309646714, 142876103, 205315390, 314894458, 359119849, 14973877, 52639682, 279742907, 272708691, 368789702, 195192251, 387795092, 224107982, 140069074, 189668896, 143648768, 371354104, 78473037, 266896588, 293631811, 359381412, 339892783, 68383666, 328568778, 328594183, 289179209, 81772250, 166140729, 151823105, 24833777, 325315809, 233587705, 195625838, 293066227, 331236762, 208172879, 378335092, 334874643, 306153299, 338808170, 361524190, 236246373, 296009894, 335400790, 387244233, 448111, 139432856, 152045255, 257751613, 136619307, 301776003, 392041342, 352627528, 206670493, 85343055, 105110019, 212343624, 220083482, 383318653, 343160016, 251644367, 30899823, 157387135, 265891532, 51772453, 280808567, 337362935, 161321516, 382051688, 196496983, 277743265, 297275039, 131970027, 45719208, 310048645, 37603260}

1

395299422

Returns: 209562027
486272

{113095571, 330802881, 245623480, 238312401, 100497127, 121139193, 350561320, 147596976, 12903922, 338960960, 51398888, 212081701, 25750261, 195598426, 304880784, 339856378, 32940057, 235129065, 20911474, 57069388, 137299534, 183282926, 353738927, 113252580, 197303303, 5417211, 185926697, 119014455, 113414165, 105131117, 99537480, 181264390, 125961610, 208402006, 32177296, 356557854, 62268672, 69365247, 327494899, 272876125, 332925365, 225026439, 175220241, 195203264, 240873685, 260925420, 247804454, 266302441, 318305485, 90830961, 19518346, 223881473, 318279161, 272532742, 293028895, 249450465, 173156132, 198956528, 232567586, 91516482, 279107218, 348299193, 297369606, 286997174, 123097456, 266535784, 220812909, 24924973, 188688280, 163379711, 335156906, 132146892, 251958074, 131325299, 109544837, 49346867, 267694186, 355700831, 202483374, 311730295, 116566920, 267303503, 12670130, 172145278, 133450376, 103956457, 177429986, 392123320, 314878126, 277659730, 120288866, 9345399, 211956280, 380310504, 21792827, 273912171, 312922745, 179494811, 298141203, 291222232, 175636520, 185527172, 339983902, 274282902, 246695540, 335143512, 18772783, 310285967, 319680450, 99133440, 50737806, 111132177, 33920202, 134449523, 309646714, 142876103, 205315390, 314894458, 359119849, 14973877, 52639682, 279742907, 272708691, 368789702, 195192251, 387795092, 224107982, 140069074, 189668896, 143648768, 371354104, 78473037, 266896588, 293631811, 359381412, 339892783, 68383666, 328568778, 328594183, 289179209, 81772250, 166140729, 151823105, 24833777, 325315809, 233587705, 195625838, 293066227, 331236762, 208172879, 378335092, 334874643, 306153299, 338808170, 361524190, 236246373, 296009894, 335400790, 387244233, 448111, 139432856, 152045255, 257751613, 136619307, 301776003, 392041342, 352627528, 206670493, 85343055, 105110019, 212343624, 220083482, 383318653, 343160016, 251644367, 30899823, 157387135, 265891532, 51772453, 280808567, 337362935, 161321516, 382051688, 196496983, 277743265, 297275039, 131970027, 45719208, 310048645, 37603260}

17062432

395299422

Returns: 422943593
467434

{23962313, 57970642, 76891728, 54090915}

0

138022219

Returns: 601706339
467434

{23962313, 57970642, 76891728, 54090915}

1

138022219

Returns: 974273239
467434

{23962313, 57970642, 76891728, 54090915}

91165974

138022219

Returns: 373841515
500000

{500000000, 250000000, 750000000, 125000000, 375000000, 625000000, 875000000, 42, 17, 13, 666, 133742, 42666, 666666, 666666666, 13374242, 42133742 }

421337

1000000007

Returns: 599639811
500000

{0 }

0

1000000007

Returns: 817756556
500000

{0 }

0

1000000000

Returns: 817756556
500000

{1 }

1

1000000007

Returns: 284021446
500000

{10000000, 10000001 }

1

1000000007

Returns: 258280401
500000

{10, 20, 30 }

1000000006

1000000007

Returns: 975716063
500000

{1000000006 }

1

1000000007

Returns: 284021446
100000

{1, 2 }

1

1000000000

Returns: 612815053
500000

{23, 31, 123, 1, 2, 3, 4, 5 }

37

1000000007

Returns: 446887857
500000

{0 }

1

1000000007

Returns: 284021446
500000

{0 }

0

1000000

Returns: 817756556

Statistics

Problem Statement for "SimulateBST"

Problem Statement

Definition

Constraints

Examples