bitwise-ors-of-subarrays_test.go

package problem0898

import (
	"fmt"
	"testing"

	"github.com/stretchr/testify/assert"
)

// tcs is testcase slice
var tcs = []struct {
	A   []int
	ans int
}{

	{
		[]int{1, 3, 4},
		4,
	},

	{
		[]int{0},
		1,
	},

	{
		[]int{1, 1, 2},
		3,
	},

	{
		[]int{1, 2, 4},
		6,
	},

	{
		[]int{530655536, 928078641, 321189591, 433348369, 368148846, 244673843, 935344340, 420292413, 802812842, 135640995, 520631925, 999129109, 225698369, 600346256, 559988972, 839784923, 456990771, 178246718, 308836641, 9242427, 61293926, 444870028, 618485197, 430197532, 151462860, 756059866, 575618363, 980126270, 559249004, 278111112, 220022472, 873721074, 995495324, 680558741, 281152893, 228088262, 828192401, 409220507, 676333585, 61874245, 622417672, 319124744, 569998772, 21055136, 325998969, 816437667, 39728988, 865273979, 379564726, 666426462, 954173567, 620212914, 653921867, 396611097, 314381640, 192828845, 915350101, 538762791, 343732646, 454249966, 127449168, 336328759, 635965386, 253575860, 621845032, 524471161, 141500781, 19665639, 837705535, 888053144, 191136767, 243591733, 694994005, 634783856, 669090696, 202172146, 361953009, 558462431, 442270553, 603459833, 91745235, 296539372, 139571372, 459605680, 925409904, 870556316, 789969050, 114846316, 292394258, 400728851, 119952885, 318577840, 298673755, 866399606, 906840482, 258819285, 705827935, 356722865, 669344279, 625367269, 717179880, 607717299, 411333710, 698779345, 26241552, 35404654, 154674449, 452768565, 102125350, 104953608, 881647237, 20745039, 459112502, 584192613, 213059203, 489674007, 576169704, 179055717, 423121361, 98163359, 244758426, 783341838, 18342205, 629853039, 510618595, 397044210, 429283438, 300216262, 402011520, 802712481, 946957766, 605582898, 909742104, 741648369, 516885886, 538523761, 164786455, 831785761, 173534064, 96918956, 177349204, 924754694, 638114449, 276674630, 671554258, 141991901, 900765459, 141745953, 704038254, 424882954, 37306863, 472247511, 569758486, 518469037, 235911823, 846688692, 303848304, 313423879, 632939188, 331104243, 517167442, 571055004, 266597871, 532608599, 296550877, 71993133, 762653468, 902280359, 789429097, 280250899, 14522378, 12643255, 502708413, 121774119, 783841941, 256950120, 262811378, 443354332, 254757044, 302985827, 262962504, 225722777, 319973037, 535978045, 840021548, 776860444, 753730714, 294066027, 952586930, 6514649, 286004792, 172702655, 637057474, 228715955, 105126015, 631615602, 869546624, 621774628, 530823095, 850851686, 114273855, 938790033, 115853565, 4749870, 955668289, 654223219, 171395367, 980279694, 698312020, 181353540, 462277167, 545194856, 224866048, 630979957, 943463621, 30190301, 853262246, 882986362, 22847439, 364928740, 953901210, 633505688, 38747191, 170033807, 229801458, 676004518, 75797397, 671245659, 823752370, 190615238, 570427636, 305352045, 560907620, 547653017, 686443946, 793805564, 636437835, 799056222, 457277848, 775008212, 841952374, 228857728, 234822155, 934424262, 706342550, 705900503, 623388192, 990147572, 886178585, 836493633, 171673887, 831500449, 711161010, 132929746, 280635769, 733519030, 316220544, 290754059, 654146891, 137456046, 223722543, 206168321, 715538503, 289962750, 608810889, 161589860, 824289995, 847862068, 984131593, 115738291, 778750356, 773861760, 257069501, 486063852, 775076393, 176854587, 359223345, 482417861, 697396663, 855261682, 594439310, 648078429, 743733268, 636669294, 769690723, 926990758, 889896532, 123427813, 34741679, 916437670, 140719166, 69051506, 456106260, 256535700, 795166886, 417653361, 791926546, 180398247, 750671851, 346140241, 609215214, 694735107, 856435584, 134015212, 614119121, 120673547, 744054980, 837344526, 350047981, 423306961, 552443876, 634648822, 379984981, 730898698, 87932716, 181028315, 649326619, 467382122, 212012221, 389292635, 35623804, 740348959, 298027524, 843279976, 213016500, 459412052, 317721420, 77962264, 764693639, 649143437, 159422738, 837780372, 348136992, 236345789, 498119322, 715373253, 482423067, 655449219, 834193190, 304088958, 1399139, 991096681, 732703820, 325160663, 468819853, 271586829, 96535142, 503334694, 910374575, 82747567, 354731446, 283598043, 585477712, 245161151, 345776310, 245524170, 9971459, 710823468, 90343051, 123580293, 670899635, 901223684, 539344677, 942927808, 383344232, 775261154, 202458936, 364178337, 644496289, 420449342, 734707612, 518230769, 59344459, 113448314, 957764320, 722800277, 460574296, 250371045, 379915120, 599673628, 851147271, 695258038, 342136141, 363429491, 170826906, 109926145, 917978489, 295445029, 156304005, 356597317, 614824142, 372859922, 787394040, 235867284, 284707523, 7622007, 274575480, 622054108, 248793728, 339813479, 401838598, 441875846, 330115950, 269866102, 716286283, 286158638, 11572337, 563336190, 371870126, 742575522, 30438828, 937785813, 786710077, 823038461, 202384911, 342611080, 987709284, 624342632, 553949432, 8790920, 638595095, 693713228, 634231188, 502798901, 752111301, 866853308, 366337798, 543021245, 571228126, 10653565, 752019642, 215522510, 913531723, 32637793, 250432799, 468386440, 466275456, 558222995, 735968948, 484684316, 48069686, 319820898, 439098336, 849599740, 55716616, 988684711, 809762536, 23195589, 302168113, 624021401, 57717807, 205903394, 999606167, 719055284, 652468784, 182863872, 727267875, 809921633, 217314117, 722259144, 446443226, 557203139, 341526448, 787175204, 379807766, 528932772, 858483055, 473807317, 988310021, 949758851, 198406027, 170469128, 367240443, 846011417, 125237977, 115514749, 975852386, 175941972, 393486961, 227653615, 857088471, 564458163, 419985867, 562747630, 660951237, 418860726, 602360353, 693036985, 803839919, 826954844, 474935241, 359639502, 901839521, 363248174, 651299096, 957637512, 662961732, 303239473, 587068005, 416770784, 200458495, 607470333, 36616013, 376261616, 815543449, 13744402, 332491172, 27391235, 283190, 458407034, 554084351, 646130004, 886184356, 947514802, 163019319, 591340865, 735198697, 931436390, 318580482, 382355901, 364322477, 787220294, 400681363, 589019478, 414844354, 902082200, 278544545, 336678839, 829438385, 133085758, 566196035, 468622812, 580350240, 60444553, 555204701, 527383566, 15503986, 990278321, 889721921, 576344425, 318755567, 224221164, 509948579, 554986987, 75147931, 922426289, 283106239, 189875951, 861616928, 776146514, 374756970, 717185706, 18356631, 42843096, 991191958, 639721930, 641704156, 595588414, 924626440, 999390962, 24731231, 53605368, 572297980, 14743260, 593093618, 308948318, 20237996, 958028846, 792836214, 440038148, 289314269, 59830062, 949956134, 729562982, 607675645, 360754319, 406899445, 65147224, 730017685, 638674719, 148845434, 684562548, 501554616, 212546597, 29714791, 829248978, 700084153, 231681849, 682551026, 815857307, 541910003, 324532244, 3828316, 146555634, 351450133, 258264318, 529238058, 514101615, 19662010, 533216859, 245662089, 489270970, 385222250, 71376152, 650819972, 418880632, 98766933, 207769588, 305456855, 874347082, 615680533, 131077055, 20639584, 965119884, 867495264, 101489772, 967445546, 119909121, 600351654, 265456676, 625329404, 845939142, 662017247, 71878236, 704007773, 309871217, 325404462, 845413270, 370989970, 88184649, 215041482, 392046060, 998887102, 144292920, 799804293, 328066064, 484802949, 331125111, 800815394, 800552869, 434493667, 764383920, 752217734, 318875562, 718096149, 749514671, 824107725, 748843685, 551452301, 32721319, 749368009, 998468873, 537152148, 194355495, 620147611, 522647153, 117467940, 171189606, 826918795, 3036705, 196076417, 74231525, 356357753, 415152279, 877788469, 51953596, 901470380, 621144912, 709238436, 72003245, 144695588, 491175426, 832905436, 484353527, 476176576, 959348616, 775833579, 385084137, 507944891, 401962505, 753171262, 320547818, 774196305, 327158087, 329591059, 466599347, 613849165, 442875909, 32254071, 902697057, 498066042, 630326311, 337758217, 760335528, 795792494, 228786892, 518412676, 764133247, 996357455, 977770312, 557113569, 148841329, 608797940, 742035850, 624032983, 218017533, 330314539, 521199663, 768196027, 29579010, 68819648, 568441189, 725209156, 279394647, 602993677, 421141644, 612474045, 875286587, 91868159, 930036707, 767770911, 838578140, 734896235, 50841785, 182301226, 479525401, 909901538, 468148262, 364265478, 948114408, 364533780, 391303343, 262788662, 40909680, 166457508, 647101962, 609458181, 211396927, 321588558, 574216191, 390244310, 615873345, 217295610, 173844113, 866199617, 882828546, 568815891, 717250333, 351995417, 90364649, 167952330, 336309462, 947356469, 385152530, 448608774, 867945780, 228958890, 623665086, 815775429, 814053954, 908661438, 554001370, 51125794, 862275420, 245422157, 681675143, 123896515, 414006739, 304053904, 159229193, 981998191, 622389636, 954654685, 644072784, 282607360, 219203800, 330992129, 608619819, 972751698, 533313070, 838405999, 88858401, 942089097, 746977241, 926666961, 859159975, 292376727, 793660707, 698843271, 417891509, 802973267, 293553845, 987673554, 379595510, 851444472, 257055715, 927610025, 226987215, 895075910, 884570518, 283178936, 105243328, 377082077, 265517856, 956496706, 829941496, 472609076, 547087021, 685497271, 262437496, 499020508, 920214939, 202768447, 74060803, 5944497, 641997590, 691498033, 331150561, 427138570, 540153226, 370041113, 20622181, 849822694, 925800277, 190115626, 674645658, 715137059, 774928394, 886297438, 360231177, 931163449, 947769246, 51808442, 143604124, 858957600, 865332557, 530636426, 33324832, 442034085, 771058274, 61792852, 808074280, 898577167, 753786935, 134548388, 264378009, 787468173, 578194692, 681004264, 779787409, 542636893, 354627810, 689300623, 162865415, 533422759, 351032705, 881784116, 526248487, 758692081, 406013592, 943221155, 468193259, 844873781, 426602722, 13046711, 818942154, 919103237, 618174444, 967199004, 93062018, 174923809, 431468472, 283722938, 529491426, 467399914, 934021857, 799590369, 583621475, 227168235, 163250082, 555046937, 469005906, 769502955, 886534299, 580431492, 537942630, 959135032, 377811501, 125837998, 151102081, 325460524, 33676687, 168466534, 963089827, 488449525, 453939156, 641587723, 756071590, 161352189, 573227615, 879288550, 976419637, 76030495, 424952893, 498338146, 867774358, 175387564, 238601329, 84364223, 422257403, 1596289, 577153399, 440055681, 849470354, 353000862, 587949899, 569731125, 745841859, 637745065, 138525773, 731559083, 739735346, 574241801, 290241180, 735284880, 705674538, 742150263, 891677914, 632286711, 716601216, 277071972, 406073814, 488308568, 604891030, 305818763, 22800424, 717419668, 715193045, 197750926, 650559606, 520898789, 169586095, 86930839, 675363845, 996980937, 571847964, 869967309, 863997019, 724755524, 543635262, 764130212, 124244089, 698257841, 75734340, 381823241, 354193343, 257939491, 307178081, 390043222, 14427239, 23917935, 145523402, 574418021, 105552442, 670296397, 725419581, 931643778, 335776934, 435197956, 892718196, 62952343, 445081731, 765753742, 848659718, 853215425, 902977866, 291618482, 376031016, 83058178, 268193463, 635441685, 671959938, 171377448, 122567921, 507986154, 14625899, 197738764, 857568902, 971057288, 134102415, 871829033, 139554103, 342377734, 949676018, 247031829, 400122714, 386044179, 115983333, 330544640, 369667643, 524943597, 901852364, 465521890, 663195216, 841504393, 478140546, 437868847, 632234415, 89164537, 510732718, 506473529, 925857517, 844109696, 495445229, 687197802, 354761298, 657958227, 794128788, 253898174, 51707361, 663947575, 285202226, 51256555, 959773458, 985096661, 989115609, 838342002, 501319858, 505045818, 294397502, 719261035, 846908705, 719552689, 628557707, 788430877, 54114334, 649567609, 426853348, 63491914, 937067140, 337208166, 669248408, 164304553, 703112882, 362884566, 191391070, 879332134, 152391223, 44295138, 905725871, 542223549, 849580189, 472457880, 834300041, 828967768, 408429507, 960014898, 90278694, 313807136, 967027635, 541773323, 92312812, 242459550, 853057864, 73201279, 711298593, 350890103, 520249608, 958984192, 137243860, 982081484, 515046107, 864075286, 875144687, 905087170, 279703517, 37209153, 970478809, 499479499, 52076676, 658588039, 768738685, 524193201, 275900227, 212740220, 171551924, 734125356, 724451879, 35725830, 968038239, 758684378, 829633482, 564288467, 432477407, 551170704, 512597311, 159812008, 115080234, 211573377, 178491131, 448704720, 255618000, 428719345, 478509774, 715865570, 396537086, 403199030, 756158822, 19958648, 960772049, 509404505, 196210034, 901424631, 574582812, 776137808, 955573763, 392685885, 511473681, 749672950, 484736963, 374980119, 268509251, 519569263, 621018742, 73787980, 889159483, 437534712, 871591557, 276377422, 334880540, 490935183, 775521554, 769122914, 428801318, 559230512, 793304088, 190411977, 839822265, 909455697, 798982932, 165275244, 720465469, 85759159, 54437495, 191884595, 672590057, 400723689, 644099534, 428865253, 224896394, 659410733, 729849464, 560210890, 73314197, 805319102, 758181533, 50865572, 262303187, 309720239, 841747068, 248625386, 519678426, 942276119, 305505310, 467931837, 79479139, 863069758, 667609141, 707723480, 929149875, 730900623, 207697820, 644252853, 485261136, 259488812, 685211991, 535298084, 712058280, 648184791, 275314646, 459034493, 908123669, 735806843, 458617544, 774873614, 87258784, 358544966, 803731973, 998408230, 573293348, 950410096, 44391386, 227758737, 441887376, 508172639, 408170871, 839608845, 749072635, 54395790, 216135838, 27259691, 630010201, 682298607, 783101346, 592684605, 201312572, 886569216, 390349621, 228750058, 659328019, 352996465, 558343470, 218197823, 808159462, 576065254, 244121333, 280370719, 705678387, 160887305, 939986753, 668075000, 511839543, 121433748, 728782969, 9100162, 331252730, 629746210, 79918444, 444882351, 663035685, 26467866, 970616596, 322199017, 516064972, 404978495, 413804996, 909128669, 346028708, 826609848, 805419344, 97904041, 249736143, 206685558, 173666976, 544644487, 707724103, 689986879, 597359785, 262499187, 478508293, 853110529, 483417018, 993644699, 726019174, 576812057, 861551974, 350334155, 196166744, 306319461, 34395756, 182983381, 599041131, 793888565, 788794038, 415702043, 775462463, 756607891, 405782513, 30066009, 825062717, 445926726, 118297383, 842086362, 818032332, 619366899, 817042931, 588011379, 610997700, 459970639, 832188890, 762328733, 757623300, 609004761, 548498125, 441741551, 739960140, 344428292, 654202247, 191611327, 899335843, 102666973, 701874692, 498133768, 242207557, 660353767, 33798767, 405225431, 150916805, 767688694, 272574276, 61072023, 790224132, 764785932, 973340287, 133001892, 423623842, 395554769, 480781663, 42018563, 169517420, 504719737, 55810259, 183530435, 418427452, 586271906, 887014525, 317743590, 762660015, 103691670, 552875714, 288040573, 448661065, 118017526, 279232517, 394289998, 918443330, 708979402, 131212487, 161450506, 738395274, 297338228, 292736235, 620564307, 669658188, 888124241, 961482853, 159253706, 738730395, 662846350, 348104647, 15149077, 15040180, 547955582, 852895013, 172692938, 533077598, 28530281, 177751787, 268140559, 557687823, 635066467, 244529506, 563226026, 507041664, 603394281, 913876383, 988793122, 503116131, 248110238, 814146275, 859692693, 355628399, 635842539, 820526089, 647352418, 196564144, 116943652, 622204999, 990828691, 638920881, 151862189, 889612903, 745789040, 762371135, 206726240, 29037112, 210320485, 236184339, 757453925, 590350897, 170704488, 489378771, 518349322, 828840727, 384991563, 27330749, 671518838, 692962234, 160268461, 867682266, 932798449, 309874897, 943384033, 632174174, 128378884, 821751196, 278779465, 146542001, 311612236, 864241569, 128599250, 450001236, 830941553, 965101620, 820029265, 428770355, 934963565, 892942463, 26543336, 748440818, 273192827, 606285240, 171294765, 18385968, 173416477, 611930800, 323032337, 850094912, 698754471, 213472194, 386455206, 98878100, 16867588, 959943438, 687963711, 310432368, 627837228, 774656795, 343431953, 410484555, 227428598, 361762454, 23649964, 309470523, 809662023, 929501783, 665630893, 626017941, 446493142, 740500748, 826001700, 844188596, 162448182, 984746913, 255946037, 923902859, 792033510, 254921069, 13477293, 250299193, 146237838, 784031542, 210204714, 130918155, 228986292, 369049595, 889625378, 506569320, 522507209, 365960806, 382622078, 443720685, 830324289, 15261923, 205711340, 15323832, 871799113, 696205111, 750294271, 975990610, 153485431, 296156047, 919692289, 652479512, 773428875, 169240983, 698578810, 142517346, 685174458, 298074867, 104832401, 819431359, 65985310, 44404574, 422135419, 135124243, 310861583, 636349787, 75282449, 781826319, 559323301, 438116952, 163554023, 233715293, 224703721, 916211361, 207443247, 609513414, 768300139, 658844147, 568506210, 495537732, 180739366, 625169364, 109169121, 982686980, 393441826, 70911614, 526697727, 664349572, 50731453, 382504513, 210952948, 160753589, 616246550, 412339113, 695415820, 267298836, 215254348, 649141154, 811042789, 279526826, 81909736, 732680160, 652643570, 802579699, 863303092, 837148579, 906184587, 670926647, 917239717, 97580270, 234406450, 577354774, 352872339, 320452466, 497780315, 588784161, 908779798, 502099700, 774307059, 326664186, 606902131, 928604677, 566969749, 806176493, 325586691, 45455591, 502095128, 118790605, 83729077, 941569521, 396274251, 102741462, 382033834, 800503895, 225116762, 855853282, 850985067, 906096732, 216800396, 220035577, 725748857, 303918990, 165622030, 573273713, 7299062, 60711486, 249046529, 370730722, 272129223, 729145567, 537447982, 832624466, 698209660, 583274433, 769900342, 743918446, 558986699, 484159982, 938552445, 929900504, 669853082, 387068389, 700053058, 637158088, 997809191, 656791472, 427982003, 279135025, 699458209, 694953874, 164028672, 747407724, 287483322, 4800403, 235039817, 641804285, 515774874, 390953823, 602744039, 613092486, 796871222, 243116207, 972878934, 220790804, 958118550, 408193403, 210736493, 539314887, 345049706, 158417907, 554679724, 503764222, 598221415, 253692739, 245951789, 124317235, 342123517, 260052135, 709444593, 444741343, 480560792, 97270102, 593221065, 645567301, 144859661, 775500760, 759811013, 292823701, 332248910, 124771537, 972787629, 638909369, 278380896, 170199561, 628381488, 923954877, 849562324, 924987600, 341765076, 665243624, 619781817, 871407612, 895181067, 150404282, 954865788, 488955991, 356165993, 898798302, 110927181, 646767030, 182454193, 800780021, 965824091, 640597826, 264469272, 37504824, 799618475, 523354912, 146926535, 120806538, 624224960, 535878449, 551324502, 673448381, 705450531, 234011672, 882171498, 466694777, 711746632, 747005335, 165476350, 118714747, 636241889, 709602352, 482550331, 176078811, 590781481, 356174582, 644246516, 65078580, 786810925, 819313435, 129105070, 395935332, 790209347, 475305234, 926212160, 515470275, 927674602, 555353306, 119218784, 631466298, 595823719, 280218827, 67370855, 303386114, 391153221, 203779404, 246686879, 883992445, 981360850, 910542680, 67750873, 824568732, 467146269, 964842667, 762194758, 383637427, 98742072, 178483706, 59440986, 428707803, 252546104, 926209334, 21543310, 804358989, 87963226, 322188832, 430034099, 258885156, 797697651, 523092948, 475298539, 428738284, 11327608, 965621934, 523802759, 97480537, 559938585, 757376462, 468611695, 209927164, 621696521, 966530963, 338932325, 978434291, 175847137, 798010732, 461911263, 820883336, 992047866, 785440894, 818414607, 518833532, 729901137, 401657143, 134669556, 716971916, 639710792, 882272160, 378563920, 960015269, 552134774, 817213981, 172695419, 933476010, 828721858, 891248425, 447507490, 827140634, 205176045, 817576495, 129625625, 267337670, 640223363, 976484621, 438823203, 619321331, 72549610, 563909637, 786090074, 233195485, 282000408, 822322257, 732540837, 659018171, 730364098, 69161511, 91717990, 238678976, 394295957, 408525576, 792912910, 394302841, 711807371, 726774141, 995973354, 237343843, 391742131, 543839995, 574111282, 136772395, 659005921, 771122534, 607750377, 470683899, 636734664, 801184593, 812789400, 337626212, 224809214, 935934136, 823163420, 564452442, 962713789, 82269552, 468932607, 490172046, 687089529, 768277733, 336222352, 427957023, 581867042, 757160651, 937259497, 339476642, 638978097, 389212742, 477714383, 694932052, 588399211, 737894147, 83766649, 675409010, 615763214, 200459126, 870833028, 180777826, 269294076, 623017566, 286538156, 88124552, 682000641, 689606726, 918429007, 563507307, 873360562, 970133147, 980833321, 218496061, 414966033, 628801581, 833695725, 334323273, 945888523, 96260890, 808835191, 546305749, 17410437, 788505257, 117235238, 980535199, 696066423, 802063758, 46654191, 656288667, 117760215, 606837132, 779041380, 269256744, 934474781, 58302571, 973486974, 385093945, 402417524, 353733278, 715338240, 393165821, 541938705, 887722138, 510676130, 22887649, 191130572, 583585556, 285126289, 794508926, 629355353, 810812298, 11138788, 885751157, 801020720, 155832600, 443562373, 677529647, 532819221, 538057234, 861345991, 278129691, 235240013, 630224203, 513436010, 41969914, 315320771, 112512865, 304735790, 462299628, 263724880, 539359109, 367295235, 708352639, 273514634, 292527186, 203352191, 329958072, 225281078, 271286045, 573983549, 529222715, 854419519, 632234599, 936439778, 181344828, 400901962, 464266790, 614572029, 541551645, 803775030, 168433586, 740852788, 275654154, 275709948, 695707145, 156940333, 411434841, 483548197, 710535555, 622302255, 403099577, 584468017, 747258874, 488244736, 210779744, 905582486, 902066596, 957582593, 411206343, 483571625, 803543211, 976948901, 799259730, 394720218, 537391355, 622004441, 466512392, 503256717, 350264162, 911689384, 403108804, 378743139, 840456167, 473622153, 998034594, 70642958, 837682978, 361492462, 562960588, 47544889, 660059853, 487618158, 860826481, 834046500, 260848227, 761441833, 698060210, 268971753, 195993798, 214106622, 41265063, 469323422, 564150184, 741927954, 950007368, 361233027, 379803151, 74715037, 860741914, 127576419, 96862192, 195047536, 875876455, 353190304, 108672899, 81263957, 252308829, 757925787, 905099541, 716311184, 180654650, 333247786, 133236849, 789372981, 218976532, 949975655, 973893372, 780744998, 630033851, 451914471, 619790591, 139958015, 812559603, 860597950, 561283947, 66386643, 142168667, 615867857, 459105367, 904528454, 474073767, 550928997, 947534173, 149723272, 215416051, 691878341, 869753212, 399446378, 803375998, 965065721, 518866187, 201033706, 804449084, 858397460, 816850849, 951111453, 260747319, 142501296, 636115045, 280712431, 847034914, 156744459, 466665120, 56548829, 65680009, 695889090, 497804508, 523001131, 144216652, 88592160, 701619079, 377250083, 317451008, 194387734, 786221043, 207034718, 449503942, 549807191, 573890799, 138403017, 436558917, 591187498, 742753156, 877161889, 853326616, 818748336, 243753942, 131648694, 695225315, 129388228, 238418217, 648916129, 419435637, 67152945, 859353274, 309051543, 775819598, 554320869, 672329985, 629708486, 337555732, 85291431, 846566179, 56195921, 790708680, 916723429, 97062059, 404617193, 642713490, 978839672, 160427061, 464787674, 232658480, 140758624, 158426935, 306087777, 60146592, 739143149, 590691270, 480228944, 751021659, 183912288, 231405247, 761274058, 793156786, 339742941, 144346777, 887474383, 7355448, 765568771, 516666124, 803677562, 468765587, 916858179, 877528256, 419961677, 871611111, 123818806, 106897460, 198208616, 278659738, 576064081, 860207641, 495889609, 233892033, 401133501, 48266857, 48621606, 819794935, 792396372, 846567053, 654052331, 164582094, 817104977, 982569902, 633496245, 221390154, 843550784, 280055238, 281641297, 19023741, 211860725, 476861067, 353283503, 171924066, 12404874, 699392211, 817897657, 368046748, 666490894, 432304656, 213751827, 38221437, 156730461, 591421321, 560695259, 463158087, 506259472, 748014837, 336744332, 522850752, 853149834, 685924528, 50043174, 104374614, 776567583, 758410071, 132636843, 22783718, 400844101, 140951446, 498703700, 294201046, 195511629, 399145996, 265054378, 945241686, 880285229, 911002299, 558992962, 529948612, 985215175, 830710462, 775977662, 319184503, 753939465, 404439086, 737018999, 459536186, 82659815, 444203013, 657965787, 500255983, 539456806, 949840014, 331261442, 874770277, 69955892, 647940019, 731884343, 49686299, 144676304, 212716247, 794011141, 31236451, 589124411, 308478090, 533680125, 269175743, 1178750, 1461502, 957633006, 263694179, 805047960, 140021926, 287320034, 580524028, 886732852, 339603541, 978799317, 327334915, 182276857, 382253882, 335262465, 94828135, 902394678, 586384312, 251922363, 989222351, 119746409, 738020062, 241157582, 324131931, 943252307, 321626638, 410078825, 560767279, 311505875, 303153744, 670975663, 604064725, 711826981, 354427925, 100926691, 554748580, 753289254, 658003199, 526561583, 826109612, 482470102, 744130143, 595583840, 440224354, 33775172, 474609376, 862235902, 876351312, 801271143, 327575355, 288324896, 425787099, 941855052, 878748572, 652999311, 593926808, 323139753, 448866799, 761537768, 224788685, 564199740, 419950081, 138835325, 157162448, 918518463, 229781043, 162752546, 803985988, 36237700, 734801304, 943846762, 438254587, 650448003, 525091525, 703308020, 716237083, 672012293, 674350759, 76036496, 682901298, 226949829, 83558187, 452351953, 158815624, 504378526, 127514973, 906239825, 296394950, 19804473, 499630603, 956177746, 361234844, 248049773, 853700339, 485273656, 572333161, 291650424, 986117348, 463429370, 21203090, 339728783, 97564928, 237265248, 723808022, 748312590, 439550973, 55086048, 422234095, 516245775, 470201486, 833021621, 769068429, 630981441, 282387912, 656384006, 715639298, 906030725, 744589867, 425974272, 902457237, 652064056, 685928545, 538809869, 306003586, 902399949, 433349986, 365349227, 229465474, 570735010, 823956184, 207950081, 311098833, 282392534, 582014532, 668383264, 881999692, 433746032, 877343632, 859141793, 420520441, 934110487, 473949242, 646311718, 641467593, 325412904, 556643167, 757313170, 887773099, 373897157, 571608955, 394183179, 383029922, 831123899, 836157353, 122621507, 539259358, 180320576, 124219203, 670195088, 330374454, 330988348, 633952682, 187622880, 588375571, 594121601, 575448812, 49141022, 742917666, 577995615, 583814950, 600228498, 193744677, 604098053, 682915731, 625212201, 632937454, 502418584, 915332122, 115719042, 406749840, 280372534, 755044979, 319211009, 507384162, 296458390, 548147486, 249587698, 11836626, 25741671, 614543254, 471008564, 262507615, 235439497, 400588424, 828009396, 693282611, 629501143, 321920214, 175447744, 169740896, 322798049, 366247436, 842974619, 225178254, 473960048, 161312326, 867188547, 323196539, 604369303, 741656654, 187293173, 349234625, 577419728, 343232255, 243655869, 942638882, 594242091, 819468675, 28591772, 371584345, 81493995, 449559149, 576397975, 647576431, 139213469, 745109557, 202164493, 468746338, 496537915, 559944679, 191915494, 695282728, 277292042, 495947018, 641632755, 111497866, 263113405, 60826313, 577486286, 65246205, 156492408, 635473964, 559274791, 198229013, 423700390, 319353632, 366742291, 375383783, 870496329, 513843707, 326194231, 595738336, 773645857, 949405460, 860143850, 223896466, 902000944, 915537214, 641516217, 761377407, 194618847, 583494828, 128287219, 269409489, 654286347, 725175099, 389801571, 758828617, 164645813, 643686935, 624658648, 52575635, 973836399, 334185325, 101197129, 998719476, 568203797, 255637013, 717374115, 148088087, 994281088, 321497519, 580599870, 581340896, 502657196, 894834642, 286241267, 330527681, 944611010, 45047166, 603757743, 279920384, 173122333, 861599666, 762652681, 611880298, 829369331, 654691655, 874061435, 812171670, 762390787, 840972353, 200470598, 690109045, 357005864, 842683990, 696589229, 59541454, 614377729, 278275377, 384289648, 705968155, 305538789, 47934553, 950013145, 244492197, 252057714, 680560438, 685938568, 624166911, 217740838, 47278883, 930834901, 48851288, 460540927, 200822142, 827023229, 268859553, 640204474, 711196768, 333368062, 167503464, 656513964, 203634541, 488114969, 523119815, 191274317, 319331326, 21784920, 282447495, 37956495, 883632266, 521853859, 93178470, 326611905, 636394420, 413541517, 595699362, 536650623, 981921683, 356639116, 807233372, 645429209, 732500109, 868754682, 876290443, 437209008, 982352473, 804157149, 643628342, 899998635, 147931676, 141013527, 30444891, 831337751, 116241967, 583470112, 365550547, 352011543, 882772328, 485673721, 769633562, 228716613, 791779909, 296576623, 570698294, 161343662, 945706227, 910664298, 185871486, 313035872, 676006652, 850218993, 644419057, 301234523, 108527500, 265903438, 623086072, 639268535, 121489258, 696407503, 836425962, 635879149, 626893905, 439856257, 489197050, 577978659, 840334831, 245368825, 186251767, 69672784, 150057178, 210649992, 530374697, 849445731, 560212686, 804087514, 982790640, 547219182, 244204727, 270543947, 996766190, 834847921, 336526959, 422953445, 882194985, 226702683, 659167416, 813663031, 824750068, 472819178, 891930829, 620557260, 750329860, 516740580, 207609471, 450809564, 721470651, 184233427, 678505237, 449943848, 335575504, 265162202, 995408933, 579784500, 956703704, 602166613, 531933391, 130936607, 283623012, 39277062, 448366875, 59802673, 461986506, 625514081, 623399654, 762005744, 39675701, 667556033, 574189318, 17210625, 310108991, 989898502, 871869387, 989859631, 339161179, 388560578, 87905648, 298033092, 312361025, 805672973, 140810100, 894733112, 114270777, 292092244, 136784015, 532296915, 429072566, 827341044, 572283409, 527529427, 501069020, 158578686, 632464359, 685413722, 31535858, 668632987, 939829588, 569307653, 779475876, 811543771, 751289678, 518984201, 487023369, 488239212, 156533746, 846850481, 336775451, 695252617, 591588201, 836744840, 82875182, 379060315, 93234497, 925125863, 491899257, 70845007, 677259069, 563183140, 93402510, 654492866, 374887786, 783518810, 761261934, 576213361, 94481817, 517473087, 60541279, 812121480, 287554445, 841788832, 863830519, 619801960, 324371589, 206449474, 181061176, 591325562, 480634613, 85461687, 36117475, 748652612, 44734773, 133213883, 355620225, 454877956, 228191243, 409653629, 482978729, 119144207, 470088667, 177675395, 429833274, 123239539, 138838396, 248936871, 961302342, 30543171, 119269577, 481307040, 25839074, 351793734, 882279911, 347107057, 709605152, 754463858, 160685079, 289006372, 245692922, 811575906, 318080152, 37400343, 209224042, 964099891, 642527923, 957773983, 306688568, 351500170, 950944003, 749488824, 228917626, 442812589, 462546347, 818938142, 721927314, 246502694, 819047375, 533354231, 301804181, 155246761, 920990516, 398024301, 216247914, 185603586, 827755661, 132504547, 937097757, 159686896, 680201237, 489958849, 291247491, 605639390, 640712222, 624543937, 784617275, 78106260, 530249799, 573272665, 945274654, 929148479, 257760751, 404211526, 588056426, 121853785, 191284067, 20203606, 432769195, 904243497, 172250364, 197907593, 503246808, 405161796, 465384113, 657604492, 500273698, 18114348, 429530952, 43348543, 594700827, 226402418, 598310414, 512639075, 916330543, 984223477, 368618946, 359594479, 839786349, 421593141, 250147236, 529388695, 3550398, 842239962, 162161302, 447505625, 641456342, 792298733, 59612153, 152689952, 43551000, 274412964, 734725216, 60803514, 291740484, 983037869, 1311716, 450866934, 500281188, 981388781, 362569883, 367687476, 210463946, 31672911, 891000854, 701327821, 43663151, 471278789, 382289343, 523118106, 722461445, 583745832, 244786919, 796993687, 992033994, 112262111, 566744895, 824724357, 202696142, 697822234, 12764784, 346997762, 833129814, 787268594, 313535022, 99515101, 822477159, 668412387, 980894945, 849224786, 586866586, 597748541, 889523095, 607630218, 697868188, 842517598, 326473743, 869907983, 157686167, 781535684, 621203308, 600804641, 388024154, 796892388, 402222681, 614217751, 155093037, 581385882, 174603588, 717169520, 205642535, 586303315, 678740453, 428464059, 446245349, 933206239, 875491673, 682281731, 686252214, 232865348, 388595414, 766396521, 922532465, 191701854, 227927997, 360921459, 704250559, 456876037, 773444029, 383774679, 465722716, 160618902, 68600481, 40663849, 487778753, 832771726, 2633569, 355057638, 765774506, 56304033, 475966017, 508738407, 1166700, 920667150, 459758754, 95889623, 45688073, 843709184, 31050986, 836864964, 477178992, 333834646, 361313826, 696147208, 108306645, 692447914, 882216026, 446969737, 858772375, 416431544, 662977172, 881885302, 727297678, 98351451, 208692862, 837840014, 662783024, 458103202, 785528643, 212081005, 777939524, 947725060, 907766036, 322768732, 898912503, 277294436, 515409636, 632614375, 512114558, 752134983, 949642223, 705117151, 853851090, 742709285, 507469717, 434532748, 180052, 924612691, 70644757, 344138341, 138450043, 473646803, 20513509, 849737487, 525041828, 659788778, 721819179, 586125901, 821176124, 315025188, 138715635, 385342297, 819672377, 698177748, 47645272, 603555243, 170766371, 129547867, 291664176, 105726656, 169986169, 796846466, 778436450, 246153283, 214010804, 640353684, 999687936, 822832579, 869719149, 142793254, 740802080, 301025868, 530531016, 263503425, 896134515, 529884461, 319308821, 415710338, 936759717, 147805512, 33826834, 458515835, 302178300, 658962478, 268806969, 240454631, 352765263, 212175277, 753692670, 822502636, 132197363, 874545414, 579838682, 593129312, 164112662, 254625423, 843092934, 801619573, 946388189, 3596568, 538974994, 651359120, 872890956, 420448975, 303482060, 57242847, 514150474, 544789707, 168300513, 214259496, 673730347, 967542088, 379496204, 42945519, 395760268, 813918295, 335876073, 497801287, 646239999, 803865989, 901073627, 791406554, 244330478, 487746010, 447170004, 386551640, 838891740, 544766261, 226629213, 872186745, 932261977, 334424560, 201122084, 656323143, 873348042, 269987830, 91644718, 831471622, 464128561, 192331895, 671459075, 375783329, 688168588, 262421728, 709406516, 959847674, 726327804, 511264255, 41035399, 692504374, 275390575, 337671249, 113018216, 113180362, 172440826, 549235825, 944737029, 875164427, 933196399, 145138837, 274494926, 374517159, 272239745, 681113477, 841298381, 96719922, 605493561, 842637349, 468463264, 223371941, 145779732, 621237833, 817115860, 280521783, 670916090, 62779831, 162186617, 540662698, 465231245, 118732405, 725150874, 265342426, 492614658, 195246452, 868948560, 326217878, 30120209, 921755601, 267646300, 940895520, 250313648, 842267782, 688914872, 636659134, 406461880, 270291025, 819346506, 6775093, 485133474, 324365371, 408282623, 812623555, 859208784, 293250026, 98151864, 925268341, 918213101, 100090356, 55961186, 418816900, 753495549, 886594826, 421914696, 251725894, 326236021, 218291838, 91393947, 71933385, 786501313, 518240112, 450061161, 598592462, 711802289, 342915369, 594108618, 387402445, 308786020, 674791912, 332682590, 36809873, 274582534, 837151186, 184710866, 15967339, 629403717, 87966841, 444472370, 229074038, 46165552, 859723523, 735397400, 790056707, 550092544, 616387449, 601914095, 420093728, 999877784, 518114179, 586172965, 86929212, 327828681, 772529624, 441432296, 975543639, 859985407, 306078227, 401356795, 719702145, 792042541, 910411007, 995819256, 511326436, 56959075, 481231003, 158632156, 556434001, 435633362, 518847211, 188121729, 874953534, 5245616, 358865627, 941160105, 525982817, 307737821, 677139331, 620423843, 810741954, 534982263, 896628207, 545020618, 807446919, 783872387, 571988477, 920989942, 733037908, 156877485, 798974495, 380168081, 498713695, 102842576, 452417792, 139699834, 605030718, 220414067, 225036942, 956751179, 273663287, 926959201, 5671483, 426905995, 975075985, 797254696, 774972346, 171460980, 612254081, 657842918, 47618676, 709991740, 234168149, 456952050, 306536017, 600969034, 651518524, 167484435, 202503886, 911783775, 788840383, 644943333, 696631250, 558805048, 69865320, 803773277, 348630797, 168142925, 886486656, 438378225, 599083541, 456816581, 935098094, 493659378, 367292705, 1232245, 606451861, 792015328, 37537007, 105647226, 384738726, 992288064, 912227187, 874686392, 269803473, 842767156, 401296861, 967979335, 50202221, 730611407, 277011142, 440355006, 198178319, 906391954, 271377245, 979969848, 671352140, 838606563, 496318039, 765522032, 529372283, 209706909, 881113368, 554301445, 287153235, 853708705, 777500324, 431682823, 169951855, 96873812, 550448445, 645192688, 691170218, 478738719, 384581000, 847155047, 845263280, 477517958, 702932354, 945480292, 237847576, 777300714, 409159808, 873662373, 442064594, 409523810, 680820046, 633123026, 76604599, 552711621, 99511163, 819826875, 412655362, 518054614, 108873956, 264000122, 620392371, 825984322, 87019144, 660892253, 416648453, 914551651, 93439787, 546399336, 519861118, 671931819, 548005044, 422525703, 137634184, 212805312, 869824349, 866157754, 235816911, 446877404, 724147776, 957251692, 36888532, 277361976, 13703309, 804946204, 111472087, 188029241, 670158597, 467892649, 707099434, 953715809, 678442180, 828612636, 696143850, 862461018, 238548793, 64988052, 984526006, 449965788, 352025977, 458148713, 416975659, 850099020, 601320047, 123383130, 62834090, 78549220, 98579267, 59683850, 177929115, 16134918, 531036895, 856739881, 418395242, 950816507, 514232505, 977543466, 698846688, 130232695, 634460497, 766232430, 905962747, 634134799, 993401029, 251572998, 676486573, 654489732, 981380828, 47815241, 586601800, 20042899, 364638559, 154935407, 74060250, 270344602, 998521085, 963056464, 140790065, 843393435, 993295826, 871535267, 534772430, 98334372, 528495158, 294906382, 792645256, 309016123, 401864545, 235297029, 472750212, 996424010, 105341760, 420412184, 945571270, 779295380, 106556293, 103355753, 36230143, 181468769, 475321275, 183231147, 994898920, 331651276, 499985564, 207503846, 736148214, 611354962, 354928909, 991185503, 787448632, 823324736, 746083534, 819465161, 187532304, 432583396, 421167840, 879802773, 367208103, 540832694, 59136142, 956778591, 672044035, 880806707, 180233300, 385234332, 584806418, 953200890, 368339596, 411665993, 258108479, 373198053, 411031644, 872829449, 486642891, 2225594, 651216637, 216200232, 375536013, 344321887, 307697391, 434230854, 875380565, 837997241, 582892501, 5861281, 172160251, 19937778, 236149098, 28800795, 555081169, 329835072, 996050319, 789999878, 161020328, 539109259, 901529879, 590492958, 462779846, 906680399, 813158064, 947754104, 531145040, 624789154, 617682534, 155712091, 129337766, 149701592, 56650903, 784040531, 915483581, 623910704, 731506141, 391856092, 487171875, 92063875, 482209578, 357026910, 880294192, 747170733, 141407073, 881944086, 771904391, 533497178, 689499078, 593718566, 234144388, 963852220, 587372808, 398492831, 292131535, 646054685, 543299512, 258922278, 411848740, 917431603, 534178942, 944989636, 60982709, 153089973, 80295751, 130903635, 490185648, 366790761, 429843510, 64085106, 778903410, 781071717, 521286653, 757896559, 684337527, 532624635, 426787858, 293248259, 801880487, 378047990, 127996895, 717928101, 430612897, 103269544, 553384892, 901753373, 833899513, 863114644, 871028760, 117532800, 323447996, 117586713, 546992450, 611725986, 555737156, 964930133, 332924962, 524669778, 889935840, 898329785, 504747628, 500202599, 967320952, 780303143, 602744582, 108383141, 564665841, 231806541, 906091243, 593500914, 9219371, 404742053, 532241381, 412789539, 692959627, 404727219, 913855035, 977296766, 169497134, 127366359, 482982783, 769150939, 980820760, 478878381, 885117851, 172901064, 842437752, 572079074, 586575138, 207538904, 565863658, 338346702, 468351194, 242884698, 865946528, 865163156, 805811711, 372494334, 192139281, 943066073, 855092827, 609833251, 325969593, 198236605, 125209890, 451762084, 586267128, 233072657, 258280054, 113800915, 893434140, 108762223, 812851409, 633242015, 920448830, 170036844, 378219952, 510576250, 427160986, 292480736, 209465994, 796547027, 457835582, 531560456, 713907160, 333576540, 444866688, 242645128, 192482369, 109251370, 964773378, 111865844, 320812754, 100517957, 384918094, 143527722, 713068761, 22598183, 374967073, 799522713, 743155113, 259330669, 716801288, 769882662, 554425144, 563901400, 905911188, 864970670, 586073534, 389919068, 455328168, 420042212, 89329569, 614041725, 529154931, 911568272, 684124692, 35861969, 286675533, 526172708, 547234350, 373906704, 69034834, 158626168, 245153447, 448602753, 677768859, 881316941, 806536268, 44659730, 996592481, 565239374, 815923052, 919803451, 997828061, 648219685, 938491554, 749598235, 219257523, 227858012, 749769992, 783599982, 884589518, 300067411, 572674833, 376179574, 539483737, 67737458, 746954245, 565241350, 725709930, 258284241, 173027539, 177873064, 469930298, 54148396, 90145094, 839815004, 71896629, 377553215, 511775165, 859870052, 934427222, 844104709, 781665649, 288171231, 341557142, 769731175, 155376533, 289736346, 602644777, 499988094, 482142157, 905765097, 718593617, 919677967, 332349942, 280053085, 938306670, 958630611, 649562435, 830671300, 896072051, 162762783, 552141131, 424863933, 459545739, 66606178, 315292162, 256139658, 756512767, 206821732, 762070138, 606482390, 121810837, 660913399, 129402673, 933492167, 943041391, 788077201, 748330622, 265989911, 568945918, 817213724, 680134040, 83226625, 783111327, 789998755, 256798969, 426431581, 23087136, 180976413, 662538886, 3923227, 58926973, 876719809, 398700228, 104863177, 323999651, 531784783, 683491905, 51484472, 641541658, 432645242, 659022974, 579710324, 60865282, 341615178, 208915242, 699327442, 465600427, 247474658, 993815399, 343743464, 6548210, 3529874, 473658657, 403971918, 792212683, 910757416, 143300380, 791869596, 205618069, 747461584, 833281283, 777295920, 879660914, 830983721, 267886116, 420302138, 7167532, 65734033, 364965042, 895916440, 455185945, 723685816, 704588859, 289553801, 817198376, 361925995, 824499280, 780160863, 821402442, 636768070, 388392168, 685786718, 151759730, 327074411, 131321076, 157450803, 559054984, 313833371, 514245903, 121786188, 850720440, 2433945, 595370553, 483457449, 156224269, 424429879, 354338464, 986873091, 418595769, 596801355, 205515431, 687126830, 485740876, 307132889, 197038091, 372246142, 468621936, 137642318, 102819588, 703986556, 109014100, 710681929, 668120664, 987440443, 162389784, 982494261, 551067739, 422152441, 959497683, 394437930, 995025745, 127311714, 506307202, 129588099, 802684890, 701532157, 791020442, 20842068, 482025054, 35892130, 328604191, 339084115, 966216753, 796196264, 785343007, 223029061, 414583231, 523157608, 914520468, 608227254, 300039679, 755197673, 501662030, 195835363, 810040514, 623160582, 342410148, 219592898, 10358260, 227034517, 21611961, 43003706, 996268507, 252755805, 826913063, 533398942, 730096612, 615570581, 234601472, 294599143, 79199785, 147475685, 787464723, 263862821, 398554850, 545241422, 380986324, 680179859, 592136120, 608373575, 110246921, 778116089, 310296955, 762001485, 451646209, 139991283, 553728233, 44350891, 947401732, 276372022, 103337128, 997495587, 11976413, 76254517, 724296611, 410627640, 318008847, 425621433, 221550610, 638391760, 487761231, 445075121, 773320485, 587658077, 821762056, 587294858, 406692267, 287039278, 691553557, 653184465, 119570830, 941818398, 496127501, 18538357, 623610233, 24069549, 373087986, 668498655, 848621488, 101885328, 453781003, 18019489, 294185505, 713869682, 977172836, 907631531, 970298342, 168691919, 388272420, 799425250, 974169388, 294324646, 53005175, 329170381, 623786157, 324319036, 876771345, 369451495, 269694154, 400242685, 815302420, 293992773, 272822761, 471661089, 45848278, 541588497, 288424467, 963934844, 232603134, 898466110, 36007870, 704440929, 407363557, 811648626, 827820387, 731808565, 750934586, 485217590, 422790141, 729484465, 360856738, 3059306, 368101936, 120838999, 36678591, 592207169, 776390431, 819769689, 677958023, 761236548, 7977825, 475072399, 128518217, 46820800, 315968517, 887823605, 257615535, 44266461, 286900128, 539018505, 393019227, 50859974, 175540764, 226515631, 603321800, 433225139, 988863672, 688246765, 960411637, 822531363, 231615757, 119131685, 355879366, 251249285, 576290565, 477705138, 607617927, 585972435, 177943269, 583143427, 774534766, 868986368, 722056172, 889522541, 438862517, 600148340, 94689233, 142772181, 514620055, 595557543, 435512676, 36440987, 749250782, 602363754, 164276830, 584180568, 709528094, 990216699, 669522557, 238496508, 78949740, 301729352, 230413467, 959879981, 325230669, 550670209, 865128003, 546737162, 499235749, 777308647, 300346240, 500890858, 282170346, 488865405, 248791409, 334147287, 708388350, 816453285, 176114429, 957939063, 886047768, 708963144, 697977374, 704971232, 918025685, 632120122, 887531271, 206613128, 380832883, 706547402, 734619578, 378996759, 825975760, 494617547, 427347432, 659804776, 386773363, 52304702, 56924900, 310212051, 586691326, 90908552, 122390863, 716251656, 942248484, 682415058, 737074528, 436318097, 767305627, 819021923, 397877645, 363636954, 866056078, 479246540, 646928330, 592177953, 131864218, 707805721, 588661130, 819649589, 692117001, 644337523, 726171866, 575372698, 285579003, 563857792, 545663267, 305770135, 269299931, 43250086, 953969848, 383335298, 225568858, 813939478, 696767501, 439847794, 476097217, 895749299, 305320750, 104033263, 578392145, 113766013, 953740400, 872775389, 271840925, 623336895, 592115780, 851162017, 582768715, 341022716, 198703208, 177080762, 381955353, 30430394, 833266985, 723965441, 864032355, 944277486, 748385678, 509012418, 593693896, 335329096, 350631997, 569487549, 267443673, 833703097, 168296111, 795026893, 53475082, 209743814, 215050414, 314719065, 570500925, 610798556, 548014586, 93219050, 429735006, 907937966, 937839127, 297954056, 628331297, 801802585, 930528779, 826281378, 680190339, 960733802, 427535202, 20740255, 382981666, 486105223, 838351314, 212100613, 188528009, 211294762, 128019468, 907977594, 10205221, 250757692, 533958963, 356284943, 933489330, 473547811, 895551926, 387173515, 108015703, 183586968, 19446759, 196913431, 482787458, 747269219, 37899043, 90700746, 184220044, 433428930, 419779650, 700461814, 375816557, 636982812, 56327803, 771275194, 414396165, 392666456, 830820859, 630977952, 913261644, 654782456, 851203558, 172849301, 199175644, 158712322, 202973249, 228958858, 639335656, 933651652, 694498898, 931852394, 940598537, 661107129, 313457555, 548316638, 651038241, 156256065, 454065506, 646271223, 660430208, 944512758, 997836610, 807588258, 861770194, 631032200, 198767246, 149612733, 946007698, 332125353, 767160056, 256725611, 61915975, 796523526, 6461577, 888532238, 682840214, 989254528, 529007925, 871500558, 972311554, 49136173, 940966952, 609881654, 346058363, 258601583, 822705382, 555619968, 546495208, 33355632, 582158518, 376094423, 377314877, 109012397, 562625298, 460675835, 72848863, 40175791, 500986535, 605668884, 328914416, 679186061, 787332209, 966259518, 874952833, 907768858, 548995440, 910852962, 216373601, 741069045, 842835493, 669237279, 268927126, 620207641, 496485599, 405590386, 260835794, 93381747, 28069217, 230151615, 925376271, 946197680, 49519012, 760051398, 185733717, 750686951, 934176884, 999690003, 737620331, 336994517, 880193083, 115067519, 387151027, 71933570, 915430219, 690019207, 70415381, 84430381, 618510196, 341258986, 759839554, 448521996, 146685527, 543712436, 352763876, 93107738, 825085744, 894186729, 686951667, 971024177, 508711332, 926126173, 970500519, 221978322, 870385137, 934250717, 739401950, 363083566, 43378335, 453042975, 847720290, 125879658, 745171024, 82104732, 683403978, 373561365, 340085436, 962297864, 935576511, 185489514, 99739329, 977232798, 430526400, 565570301, 461509967, 300107580, 798317091, 570463834, 359349925, 989743110, 497096487, 331995104, 754339462, 614050726, 869316332, 77064807, 764157035, 810422477, 164784290, 896246113, 650915167, 388737822, 702314708, 964609734, 209685027, 189971786, 324616996, 106540882, 608830818, 119563576, 3058914, 308836524, 278081051, 576172772, 251887389, 713418859, 349490038, 720379091, 365105188, 775159137, 152588694, 100912429, 832849921, 507885523, 737697148, 725994404, 744328532, 198906889, 480578480, 54805002, 54474587, 919906015, 265051738, 462280777, 810550510, 804357584, 603824122, 655421135, 968270273, 696764835, 601397497, 986710172, 137934441, 730296669, 181876371, 195284852, 156587911, 280151811, 79668537, 618758786, 912255998, 36763440, 468918542, 261842521, 124742670, 402181587, 956307800, 359302215, 224687918, 618757581, 409588132, 457357683, 652276564, 82641982, 3000029, 940376792, 750137092, 319384231, 475481080, 834055693, 164416300, 601000540, 50424970, 333721078, 354848138, 765407464, 882498361, 403648102, 836079123, 248038824, 351275683, 294884371, 609519174, 952334941, 536694766, 130453658, 687970810, 306131845, 855571363, 529868521, 865671170, 749044693, 716672811, 923884347, 546151229, 867313129, 353889640, 364975371, 306622369, 468733099, 642473829, 914125240, 412097603, 292154597, 950687500, 843237528, 791025913, 516221152, 199933385, 961029432, 308014700, 397820273, 115997954, 533956215, 560114662, 96508152, 5657528, 965570091, 560103363, 471910206, 90381073, 993960455, 344158979, 423462656, 498536712, 216795332, 4788407, 502795944, 769754181, 406454389, 731645472, 520806212, 696301111, 185796972, 690052977, 75044155, 600813974, 806497114, 732227888, 378416075, 133744649, 136396823, 586052600, 57296287, 479039736, 744997979, 855597174, 86667473, 938405734, 677472929, 556784569, 998181506, 149194723, 676607822, 272597146, 130301873, 554428409, 732689840, 20874904, 908283204, 722489186, 841665236, 376145436, 929535614, 363832905, 337319497, 625944178, 70758268, 951903862, 551344434, 810462249, 536468603, 219503118, 687169808, 929574489, 808101058, 359486553, 347225643, 576930946, 417360386, 3329032, 197693666, 975162746, 801714206, 895794803, 886270285, 66369355, 435382822, 205933435, 106138794, 808619969, 676033730, 176796226, 722283829, 161063191, 383174325, 200158330, 186008006, 247435890, 668610562, 845328954, 217211323, 451985424, 666497651, 293995987, 511506481, 348377533, 47582578, 157815818, 41103456, 60000092, 695443282, 93800930, 784839550, 968145173, 752837652, 466189147, 35554215, 362917443, 551733399, 639175762, 369141514, 469459025, 733529711, 540366352, 846075197, 108123819, 402057496, 791121975, 673122780, 765959199, 119874001, 317238847, 877248235, 105673171, 789353252, 572656305, 967624498, 492153789, 65887084, 219919253, 776534108, 390692757, 196433474, 978342517, 35069065, 291353487, 599911979, 676946446, 312032250, 447463174, 241512195, 890378606, 53777113, 185858508, 985091242, 665725801, 90670500, 840049223, 220783907, 17799964, 212554815, 814765489, 923606375, 503829867, 422846930, 419597683, 541334861, 138816727, 678920213, 16168517, 892631744, 337980182, 450691114, 810998497, 955955638, 927578939, 768290526, 401284843, 314003245, 158101178, 991720754, 683732062, 214303153, 184766129, 222302705, 778113421, 504354270, 162637291, 530710674, 362262307, 2811227, 516679778, 361436582, 523992068, 457519531, 54740508, 909096148, 967440652, 665324618, 888764591, 876946744, 593106900, 891056000, 929801901, 57758754, 267471814, 43873246, 992740082, 26772310, 643786251, 883390177, 797945328, 65252516, 469078816, 527220000, 201720227, 460210846, 158289008, 59245903, 692324063, 925710201, 459606499, 606580397, 825597607, 824971214, 201517398, 960610461, 907056275, 329879060, 812571337, 387508805, 991193196, 725418735, 606527342, 987943992, 49050524, 356556895, 771219714, 418499614, 871783994, 118389254, 275338430, 466006625, 369862772, 203833368, 14917929, 517127402, 455312181, 572398452, 446101184, 716265411, 855927469, 871359111, 140369135, 437100015, 484276304, 449477358, 525372459, 309115248, 326277795, 200269228, 838113260, 840976052, 746405029, 16862725, 244606888, 851679845, 138677504, 828914179, 560422196, 320942742, 183913669, 928794993, 813603445, 762030432, 525683804, 309698327, 784779396, 34930254, 38658947, 10532888, 479215749, 569047154, 190876422, 181148058, 161501724, 115666163, 665675032, 877942480, 995932315, 116621881, 273362134, 291234249, 262095098, 674764553, 484405473, 828616584, 189193455, 290047178, 229388324, 463136059, 243595123, 741268707, 978943108, 473866544, 953889606, 621381682, 913182612, 284711891, 605228304, 264465044, 662466665, 127754639, 882528438, 568090482, 973284017, 205351333, 280529046, 887860832, 738853831, 690079520, 294994340, 593686044, 31614554, 47956520, 487648986, 480908507, 183228239, 347576595, 128124270, 792925712, 7158718, 351916494, 366954372, 490133813, 329079626, 992837333, 716721800, 92561043, 72861809, 865693480, 443406576, 572478109, 739883009, 740775384, 661080773, 703180555, 341679433, 515858621, 978352891, 480071698, 508297069, 529652227, 746684292, 268442032, 17041056, 18149147, 687895777, 955887455, 766479705, 490146579, 645783608, 30300672, 201844195, 692631914, 589990283, 284781791, 773150348, 529208618, 97282823, 912843566, 189329436, 756282046, 490400174, 226641219, 653069797, 746597682, 694267620, 844880489, 365159711, 171116257, 751576250, 171245715, 774554815, 876348962, 72679, 550625494, 112647398, 480766880, 131795033, 203730735, 133151145, 911000868, 175853718, 915669304, 138661461, 452864047, 520929322, 392888914, 747299979, 622592554, 758709846, 301106092, 899503065, 566677368, 75366924, 711105319, 741204122, 699275276, 726402394, 882320213, 307687771, 676058177, 877243591, 189056754, 205933950, 875168003, 725607634, 975934046, 244758754, 682495709, 5545997, 205042174, 386621049, 652799295, 930637125, 594018854, 110627697, 243894831, 680287391, 598264048, 601088940, 925041594, 767028491, 478194261, 689016228, 591386459, 978267456, 291197508, 962496188, 699207052, 566502831, 326772939, 758834882, 32744888, 519293618, 620000224, 127912367, 584090246, 798003011, 680376153, 115576611, 655464422, 805752499, 874299241, 793646546, 983050504, 470407199, 665687598, 845365695, 675258725, 893328504, 544855772, 941363551, 591235690, 750342949, 227344141, 657069598, 229537726, 596511890, 812829831, 18593149, 878206561, 78858138, 81852260, 385322041, 449677685, 324659787, 87460357, 216240448, 686223360, 529299231, 900891317, 971537431, 171719009, 333573854, 759776731, 556673911, 980060872, 480289478, 992517097, 637425330, 927043462, 359308972, 198226729, 150150203, 717078614, 869889309, 372445613, 963090584, 887152663, 523665476, 396429886, 180966881, 138343946, 125228861, 975930048, 537747175, 151830395, 895644995, 374147006, 30179012, 112442473, 438060220, 348787293, 659020304, 217474080, 272084072, 778679954, 92132532, 220558153, 225194975, 884517919, 209759140, 229702360, 884899658, 936679721, 901097174, 687690273, 684753724, 442961424, 388472872, 72257155, 289517989, 356082114, 602719494, 105857575, 820490502, 663490136, 959644718, 805616097, 594014096, 745474639, 81893404, 126379358, 667338088, 697970197, 653312497, 132406261, 734736602, 198516421, 302338237, 195954723, 670411472, 716295487, 176369790, 323400315, 236806827, 356519813},
		14861,
	},

	// 可以有多个 testcase
}

func Test_subarrayBitwiseORs(t *testing.T) {
	ast := assert.New(t)

	for _, tc := range tcs {
		fmt.Printf("~~%v~~\n", tc)
		ast.Equal(tc.ans, subarrayBitwiseORs(tc.A), "输入:%v", tc)
	}
}

func Benchmark_subarrayBitwiseORs(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, tc := range tcs {
			subarrayBitwiseORs(tc.A)
		}
	}
}