/* * Kamil Debowski * For every prefix we update the canonical representation and run O(n) dynamic programming. * The update uses the map<int,int> at most O(n) times. * The total complexity is O(n^2 * log(n)). */ #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; map<int,int> t; // the canonical representation of a current prefix // fix the canonical representation for a new prefix void fix(int i) { // will be run O(n^2) times in total if(t[i] == 0) return; assert(t[i] <= 2); bool anything_happened = false; if(t[i] == 2) { anything_happened = true; t[i] = 0; t[i+1]++; if(i == 1) t[i-1]++; else if(i >= 2) t[i-2]++; } if(i >= 1 && t[i-1] && t[i]) { anything_happened = true; t[i-1]--; t[i]--; t[i+1]++; } if(t[i] && t[i+1]) { anything_happened = true; t[i]--; t[i+1]--; t[i+2]++; } if(anything_happened) for(int j = max(0, i - 2); j <= i + 2; ++j) fix(j); } int main() { int n; scanf("%d", &n); while(n--) { int ai; scanf("%d", &ai); --ai; ++t[ai]; fix(ai); vector<int> gather; for(pair<int,int> p : t) if(p.second) { // iterating over a map takes O(size) assert(p.second == 1); if(!gather.empty()) assert(gather.back() + 2 <= p.first); gather.push_back(p.first); } // 'gather' contains the indices of 1's in the canonical representation vector<int> holes; int last = -1; for(int x : gather) { holes.push_back(x - last); last = x; } /* * 'holes' contains distances between consecutive 1's * now we run linear DP * dp[A] = dp[can leave the next 1 without a change] */ vector<int> dp(2); dp[1] = 1; for(int i = (int) holes.size() - 1; i >= 0; --i) { vector<int> new_dp(2); if(holes[i] % 2 == 0) new_dp[0] = (dp[0] + dp[1]) % mod; new_dp[1] = (long long) (dp[0] + dp[1]) * max(0, (holes[i] - 1) / 2) % mod; new_dp[1] = (new_dp[1] + dp[1]) % mod; dp = new_dp; } printf("%d\n", dp[1]); } }
Standard input is empty
997489056 997489057 994978103 994978104 992467148 992467149 989956191 989956192 987445232 987445233 984934271 984934272 982423308 982423309 979912343 979912344 977401376 977401377 974890407 974890408 972379436 972379437 969868463 969868464 967357488 967357489 964846511 964846512 962335532 962335533 959824551 959824552 957313568 957313569 954802583 954802584 952291596 952291597 949780607 949780608 947269616 947269617 944758623 944758624 942247628 942247629 939736631 939736632 937225632 937225633 934714631 934714632 932203628 932203629 929692623 929692624 927181616 927181617 924670607 924670608 922159596 922159597 919648583 919648584 917137568 917137569 914626551 914626552 912115532 912115533 909604511 909604512 907093488 907093489 904582463 904582464 902071436 902071437 899560407 899560408 897049376 897049377 894538343 894538344 892027308 892027309 889516271 889516272 887005232 887005233 884494191 884494192 881983148 881983149 879472103 879472104 876961056 876961057 874450007 874450008 871938956 871938957 869427903 869427904 866916848 866916849 864405791 864405792 861894732 861894733 859383671 859383672 856872608 856872609 854361543 854361544 851850476 851850477 849339407 849339408 846828336 846828337 844317263 844317264 841806188 841806189 839295111 839295112 836784032 836784033 834272951 834272952 831761868 831761869 829250783 829250784 826739696 826739697 824228607 824228608 821717516 821717517 819206423 819206424 816695328 816695329 814184231 814184232 811673132 811673133 809162031 809162032 806650928 806650929 804139823 804139824 801628716 801628717 799117607 799117608 796606496 796606497 794095383 794095384 791584268 791584269 789073151 789073152 786562032 786562033 784050911 784050912 781539788 781539789 779028663 779028664 776517536 776517537 774006407 774006408 771495276 771495277 768984143 768984144 766473008 766473009 763961871 763961872 761450732 761450733 758939591 758939592 756428448 756428449 753917303 753917304 751406156 751406157 748895007 748895008 746383856 746383857 743872703 743872704 741361548 741361549 738850391 738850392 736339232 736339233 733828071 733828072 731316908 731316909 728805743 728805744 726294576 726294577 723783407 723783408 721272236 721272237 718761063 718761064 716249888 716249889 713738711 713738712 711227532 711227533 708716351 708716352 706205168 706205169 703693983 703693984 701182796 701182797 698671607 698671608 696160416 696160417 693649223 693649224 691138028 691138029 688626831 688626832 686115632 686115633 683604431 683604432 681093228 681093229 678582023 678582024 676070816 676070817 673559607 673559608 671048396 671048397 668537183 668537184 666025968 666025969 663514751 663514752 661003532 661003533 658492311 658492312 655981088 655981089 653469863 653469864 650958636 650958637 648447407 648447408 645936176 645936177 643424943 643424944 640913708 640913709 638402471 638402472 635891232 635891233 633379991 633379992 630868748 630868749 628357503 628357504 625846256 625846257 623335007 623335008 620823756 620823757 618312503 618312504 615801248 615801249 613289991 613289992 610778732 610778733 608267471 608267472 605756208 605756209 603244943 603244944 600733676 600733677 598222407 598222408 595711136 595711137 593199863 593199864 590688588 590688589 588177311 588177312 585666032 585666033 583154751 583154752 580643468 580643469 578132183 578132184 575620896 575620897 573109607 573109608 570598316 570598317 568087023 568087024 565575728 565575729 563064431 563064432 560553132 560553133 558041831 558041832 555530528 555530529 553019223 553019224 550507916 550507917 547996607 547996608 545485296 545485297 542973983 542973984 540462668 540462669 537951351 537951352 535440032 535440033 532928711 532928712 530417388 530417389 527906063 527906064 525394736 525394737 522883407 522883408 520372076 520372077 517860743 517860744 515349408 515349409 512838071 512838072 510326732 510326733 507815391 507815392 505304048 505304049 502792703 502792704 500281356 500281357 497770007 497770008 495258656 495258657 492747303 492747304 490235948 490235949 487724591 487724592 485213232 485213233 482701871 482701872 480190508 480190509 477679143 477679144 475167776 475167777 472656407 472656408 470145036 470145037 467633663 467633664 465122288 465122289 462610911 462610912 460099532 460099533 457588151 457588152 455076768 455076769 452565383 452565384 450053996 450053997 447542607 447542608 445031216 445031217 442519823 442519824 440008428 440008429 437497031 437497032 434985632 434985633 432474231 432474232 429962828 429962829 427451423 427451424 424940016 424940017 422428607 422428608 419917196 419917197 417405783 417405784 414894368 414894369 412382951 412382952 409871532 409871533 407360111 407360112 404848688 404848689 402337263 402337264 399825836 399825837 397314407 397314408 394802976 394802977 392291543 392291544 389780108 389780109 387268671 387268672 384757232 384757233 382245791 382245792 379734348 379734349 377222903 377222904 374711456 374711457 372200007 372200008 369688556 369688557 367177103 367177104 364665648 364665649 362154191 362154192 359642732 359642733 357131271 357131272 354619808 354619809 352108343 352108344 349596876 349596877 347085407 347085408 344573936 344573937 342062463 342062464 339550988 339550989 337039511 337039512 334528032 334528033 332016551 332016552 329505068 329505069 326993583 326993584 324482096 324482097 321970607 321970608 319459116 319459117 316947623 316947624 314436128 314436129 311924631 311924632 309413132 309413133 306901631 306901632 304390128 304390129 301878623 301878624 299367116 299367117 296855607 296855608 294344096 294344097 291832583 291832584 289321068 289321069 286809551 286809552 284298032 284298033 281786511 281786512 279274988 279274989 276763463 276763464 274251936 274251937 271740407 271740408 269228876 269228877 266717343 266717344 264205808 264205809 261694271 261694272 259182732 259182733 256671191 256671192 254159648 254159649 251648103 251648104 249136556 249136557 246625007 246625008 244113456 244113457 241601903 241601904 239090348 239090349 236578791 236578792 234067232 234067233 231555671 231555672 229044108 229044109 226532543 226532544 224020976 224020977 221509407 221509408 218997836 218997837 216486263 216486264 213974688 213974689 211463111 211463112 208951532 208951533 206439951 206439952 203928368 203928369 201416783 201416784 198905196 198905197 196393607 196393608 193882016 193882017 191370423 191370424 188858828 188858829 186347231 186347232 183835632 183835633 181324031 181324032 178812428 178812429 176300823 176300824 173789216 173789217 171277607 171277608 168765996 168765997 166254383 166254384 163742768 163742769 161231151 161231152 158719532 158719533 156207911 156207912 153696288 153696289 151184663 151184664 148673036 148673037 146161407 146161408 143649776 143649777 141138143 141138144 138626508 138626509 136114871 136114872 133603232 133603233 131091591 131091592 128579948 128579949 126068303 126068304 123556656 123556657 121045007 121045008 118533356 118533357 116021703 116021704 113510048 113510049 110998391 110998392 108486732 108486733 105975071 105975072 103463408 103463409 100951743 100951744 98440076 98440077 95928407 95928408 93416736 93416737 90905063 90905064 88393388 88393389 85881711 85881712 83370032 83370033 80858351 80858352 78346668 78346669 75834983 75834984 73323296 73323297 70811607 70811608 68299916 68299917 65788223 65788224 63276528 63276529 60764831 60764832 58253132 58253133 55741431 55741432 53229728 53229729 50718023 50718024 48206316 48206317 45694607 45694608 43182896 43182897 40671183 40671184 38159468 38159469 35647751 35647752 33136032 33136033 30624311 30624312 28112588 28112589 25600863 25600864 23089136 23089137 20577407 20577408 18065676 18065677 15553943 15553944 13042208 13042209 10530471 10530472 8018732 8018733 5506991 5506992 2995248 2995249 483503 483504 997971763 997971764 995460014 995460015 992948263 992948264 990436510 990436511 987924755 987924756 985412998 985412999 982901239 982901240 980389478 980389479 977877715 977877716 975365950 975365951 972854183 972854184 970342414 970342415 967830643 967830644 965318870 965318871 962807095 962807096 960295318 960295319 957783539 957783540 955271758 955271759 952759975 952759976 950248190 950248191 947736403 947736404 945224614 945224615 942712823 942712824 940201030 940201031 937689235 937689236 935177438 935177439 932665639 932665640 930153838 930153839 927642035 927642036 925130230 925130231 922618423 922618424 920106614 920106615 917594803 917594804 915082990 915082991 912571175 912571176 910059358 910059359 907547539 907547540 905035718 905035719 902523895 902523896 900012070 900012071 897500243 897500244 894988414 894988415 892476583 892476584 889964750 889964751 887452915 887452916 884941078 884941079 882429239 882429240 879917398 879917399 877405555 877405556 874893710 874893711 872381863 872381864 869870014 869870015 867358163 867358164 864846310 864846311 862334455 862334456 859822598 859822599 857310739 857310740 854798878 854798879 852287015 852287016 849775150 849775151 847263283 847263284 844751414 844751415 842239543 842239544 839727670 839727671 837215795 837215796 834703918 834703919 832192039 832192040 829680158 829680159 827168275 827168276 824656390 824656391 822144503 822144504 819632614 819632615 817120723 817120724 814608830 814608831 812096935 812096936 809585038 809585039 807073139 807073140 804561238 804561239 802049335 802049336 799537430 799537431 797025523 797025524 794513614 794513615 792001703 792001704 789489790 789489791 786977875 786977876 784465958 784465959 781954039 781954040 779442118 779442119 776930195 776930196 774418270 774418271 771906343 771906344 769394414 769394415 766882483 766882484 764370550 764370551 761858615 761858616 759346678 759346679 756834739 756834740 754322798 754322799 751810855 751810856 749298910 749298911 746786963 746786964 744275014 744275015 741763063 741763064 739251110 739251111 736739155 736739156 734227198 734227199 731715239 731715240 729203278 729203279 726691315 726691316 724179350 724179351 721667383 721667384 719155414 719155415 716643443 716643444 714131470 714131471 711619495 711619496 709107518 709107519 706595539 706595540 704083558 704083559 701571575 701571576 699059590 699059591 696547603 696547604 694035614 694035615 691523623 691523624 689011630 689011631 686499635 686499636 683987638 683987639 681475639 681475640 678963638 678963639 676451635 676451636 673939630 673939631 671427623 671427624 668915614 668915615 666403603 666403604 663891590 663891591 661379575 661379576 658867558 658867559 656355539 656355540 653843518 653843519 651331495 651331496 648819470 648819471 646307443 646307444 643795414 643795415 641283383 641283384 638771350 638771351 636259315 636259316 633747278 633747279 631235239 631235240 628723198 628723199 626211155 626211156 623699110 623699111 621187063 621187064 618675014 618675015 616162963 616162964 613650910 613650911 611138855 611138856 608626798 608626799 606114739 606114740 603602678 603602679 601090615 601090616 598578550 598578551 596066483 596066484 593554414 593554415 591042343 591042344 588530270 588530271 586018195 586018196 583506118 583506119 580994039 580994040 578481958 578481959 575969875 575969876 573457790 573457791 570945703 570945704 568433614 568433615 565921523 565921524 563409430 563409431 560897335 560897336 558385238 558385239 555873139 555873140 553361038 553361039 550848935 550848936 548336830 548336831 545824723 545824724 543312614 543312615 540800503 540800504 538288390 538288391 535776275 535776276 533264158 533264159 530752039 530752040 528239918 528239919 525727795 525727796 523215670 523215671 520703543 520703544 518191414 518191415 515679283 515679284 513167150 513167151 510655015 510655016 508142878 508142879 505630739 505630740 503118598 503118599 500606455 500606456 498094310 498094311 495582163 495582164 493070014 493070015 490557863 490557864 488045710 488045711 485533555 485533556 483021398 483021399 480509239 480509240 477997078 477997079 475484915 475484916 472972750 472972751 470460583 470460584 467948414 467948415 465436243 465436244 462924070 462924071 460411895 460411896 457899718 457899719 455387539 455387540 452875358 452875359 450363175 450363176 447850990 447850991 445338803 445338804 442826614 442826615 440314423 440314424 437802230 437802231 435290035 435290036 432777838 432777839 430265639 430265640 427753438 427753439 425241235 425241236 422729030 422729031 420216823 420216824 417704614 417704615 415192403 415192404 412680190 412680191 410167975 410167976 407655758 407655759 405143539 405143540 402631318 402631319 400119095 400119096 397606870 397606871 395094643 395094644 392582414 392582415 390070183 390070184 387557950 387557951 385045715 385045716 382533478 382533479 380021239 380021240 377508998 377508999 374996755 374996756 372484510 372484511 369972263 369972264 367460014 367460015 364947763 364947764 362435510 362435511 359923255 359923256 357410998 357410999 354898739 354898740 352386478 352386479 349874215 349874216 347361950 347361951 344849683 344849684 342337414 342337415 339825143 339825144 337312870 337312871 334800595 334800596 332288318 332288319 329776039 329776040 327263758 327263759 324751475 324751476 322239190 322239191 319726903 319726904 317214614 317214615 314702323 314702324 312190030 312190031 309677735 309677736 307165438 307165439 304653139 304653140 302140838 302140839 299628535 299628536 297116230 297116231 294603923 294603924 292091614 292091615 289579303 289579304 287066990 287066991 284554675 284554676 282042358 282042359 279530039 279530040 277017718 277017719 274505395 274505396 271993070 271993071 269480743 269480744 266968414 266968415 264456083 264456084 261943750 261943751 259431415 259431416 256919078 256919079 254406739 254406740 251894398 251894399 249382055 249382056 246869710 246869711 244357363 244357364 241845014 241845015 239332663 239332664 236820310 236820311 234307955 234307956 231795598 231795599 229283239 229283240 226770878 226770879 224258515 224258516 221746150 221746151 219233783 219233784 216721414 216721415 214209043 214209044 211696670 211696671 209184295 209184296 206671918 206671919 204159539 204159540 201647158 201647159 199134775 199134776 196622390 196622391 194110003 194110004 191597614 191597615 189085223 189085224 186572830 186572831 184060435 184060436 181548038 181548039 179035639 179035640 176523238 176523239 174010835 174010836 171498430 171498431 168986023 168986024 166473614 166473615 163961203 163961204 161448790 161448791 158936375 158936376 156423958 156423959 153911539 153911540 151399118 151399119 148886695 148886696 146374270 146374271 143861843 143861844 141349414 141349415 138836983 138836984 136324550 136324551 133812115 133812116 131299678 131299679 128787239 128787240 126274798 126274799 123762355 123762356 121249910 121249911 118737463 118737464 116225014 116225015 113712563 113712564 111200110 111200111 108687655 108687656 106175198 106175199 103662739 103662740 101150278 101150279 98637815 98637816 96125350 96125351 93612883 93612884 91100414 91100415 88587943 88587944 86075470 86075471 83562995 83562996 81050518 81050519 78538039 78538040 76025558 76025559 73513075 73513076 71000590 71000591 68488103 68488104 65975614 65975615 63463123 63463124 60950630 60950631 58438135 58438136 55925638 55925639 53413139 53413140 50900638 50900639 48388135 48388136 45875630 45875631 43363123 43363124 40850614 40850615 38338103 38338104 35825590 35825591 33313075 33313076 30800558 30800559 28288039 28288040 25775518 25775519 23262995 23262996 20750470 20750471 18237943 18237944 15725414 15725415 13212883 13212884 10700350 10700351 8187815 8187816 5675278 5675279 3162739 3162740 650198 650199 998137662 998137663 995625117 995625118 993112570 993112571 990600021 990600022 988087470 988087471 985574917 985574918 983062362 983062363 980549805 980549806 978037246 978037247 975524685 975524686 973012122 973012123 970499557 970499558 967986990 967986991 965474421 965474422 962961850 962961851 960449277 960449278 957936702 957936703 955424125 955424126 952911546 952911547 950398965 950398966 947886382 947886383 945373797 945373798 942861210 942861211 940348621 940348622 937836030 937836031 935323437 935323438 932810842 932810843 930298245 930298246 927785646 927785647 925273045 925273046 922760442 922760443 920247837 920247838 917735230 917735231 915222621 915222622 912710010 912710011 910197397 910197398 907684782 907684783 905172165 905172166 902659546 902659547 900146925 900146926 897634302 897634303 895121677 895121678 892609050 892609051 890096421 890096422 887583790 887583791 885071157 885071158 882558522 882558523 880045885 880045886 877533246 877533247 875020605 875020606 872507962 872507963 869995317 869995318 867482670 867482671 864970021 864970022 862457370 862457371 859944717 859944718 857432062 857432063 854919405 854919406 852406746 852406747 849894085 849894086 847381422 847381423 844868757 844868758 842356090 842356091 839843421 839843422 837330750 837330751 834818077 834818078 832305402 832305403 829792725 829792726 827280046 827280047 824767365 824767366 822254682 822254683 819741997 819741998 817229310 817229311 814716621 814716622 812203930 812203931 809691237 809691238 807178542 807178543 804665845 804665846 802153146 802153147 799640445 799640446 797127742 797127743 794615037 794615038 792102330 792102331 789589621 789589622 787076910 787076911 784564197 784564198 782051482 782051483 779538765 779538766 777026046 777026047 774513325 774513326 772000602 772000603 769487877 769487878 766975150 766975151 764462421 764462422 761949690 761949691 759436957 759436958 756924222 756924223 754411485 754411486 751898746 751898747 749386005 749386006 746873262 746873263 744360517 744360518 741847770 741847771 739335021 739335022 736822270 736822271 734309517 734309518 731796762 731796763 729284005 729284006 726771246 726771247 724258485 724258486 721745722 721745723 719232957 719232958 716720190 716720191 714207421 714207422 711694650 711694651 709181877 709181878 706669102 706669103 704156325 704156326 701643546 701643547 699130765 699130766 696617982 696617983 694105197 694105198 691592410 691592411 689079621 689079622 686566830 686566831 684054037 684054038 681541242 681541243 679028445 679028446 676515646 676515647 674002845 674002846 671490042 671490043 668977237 668977238 666464430 666464431 663951621 663951622 661438810 661438811 658925997 658925998 656413182 656413183 653900365 653900366 651387546 651387547 648874725 648874726 646361902 646361903 643849077 643849078 641336250 641336251 638823421 638823422 636310590 636310591 633797757 633797758 631284922 631284923 628772085 628772086 626259246 626259247 623746405 623746406 621233562 621233563 618720717 618720718 616207870 616207871 613695021 613695022 611182170 611182171 608669317 608669318 606156462 606156463 603643605 603643606 601130746 601130747 598617885 598617886 596105022 596105023 593592157 593592158 591079290 591079291 588566421 588566422 586053550 586053551 583540677 583540678 581027802 581027803 578514925 578514926 576002046 576002047 573489165 573489166 570976282 570976283 568463397 568463398 565950510 565950511 563437621 563437622 560924730 560924731 558411837 558411838 555898942 555898943 553386045 553386046 550873146 550873147 548360245 548360246 545847342 545847343 543334437 543334438 540821530 540821531 538308621 538308622 535795710 535795711 533282797 533282798 530769882 530769883 528256965 528256966 525744046 525744047 523231125 523231126 520718202 520718203 518205277 518205278 515692350 515692351 513179421 513179422 510666490 510666491 508153557 508153558 505640622 505640623 503127685 503127686 500614746 500614747 498101805 498101806 495588862 495588863 493075917 493075918 490562970 490562971 488050021 488050022 485537070 485537071 483024117 483024118 480511162 480511163 477998205 477998206 475485246 475485247 472972285 472972286 470459322 470459323 467946357 467946358 465433390 465433391 462920421 462920422 460407450 460407451 457894477 457894478 455381502 455381503 452868525 452868526 450355546 450355547 447842565 447842566 445329582 445329583 442816597 442816598 440303610 440303611 437790621 437790622 435277630 435277631 432764637 432764638 430251642 430251643 427738645 427738646 425225646 425225647 422712645 422712646 420199642 420199643 417686637 417686638 415173630 415173631 412660621 412660622 410147610 410147611 407634597 407634598 405121582 405121583 402608565 402608566 400095546 400095547 397582525 397582526 395069502 395069503 392556477 392556478 390043450 390043451 387530421 387530422 385017390 385017391 382504357 382504358 379991322 379991323 377478285 377478286 374965246 374965247 372452205 372452206 369939162 369939163 367426117 367426118 364913070 364913071 362400021 362400022 359886970 359886971 357373917 357373918 354860862 354860863 352347805 352347806 349834746 349834747 347321685 347321686 344808622 344808623 342295557 342295558 339782490 339782491 337269421 337269422 334756350 334756351 332243277 332243278 329730202 329730203 327217125 327217126 324704046 324704047 322190965 322190966 319677882 319677883 317164797 317164798 314651710 314651711 312138621 312138622 309625530 309625531 307112437 307112438 304599342 304599343 302086245 302086246 299573146 299573147 297060045 297060046 294546942 294546943 292033837 292033838 289520730 289520731 287007621 287007622 284494510 284494511 281981397 281981398 279468282 279468283 276955165 276955166 274442046 274442047 271928925 271928926 269415802 269415803 266902677 266902678 264389550 264389551 261876421 261876422 259363290 259363291 256850157 256850158 254337022 254337023 251823885 251823886 249310746 249310747 246797605 246797606 244284462 244284463 241771317 241771318 239258170 239258171 236745021 236745022 234231870 234231871 231718717 231718718 229205562 229205563 226692405 226692406 224179246 224179247 221666085 221666086 219152922 219152923 216639757 216639758 214126590 214126591 211613421 211613422 209100250 209100251 206587077 206587078 204073902 204073903 201560725 201560726 199047546 199047547 196534365 196534366 194021182 194021183 191507997 191507998 188994810 188994811 186481621 186481622 183968430 183968431 181455237 181455238 178942042 178942043 176428845 176428846 173915646 173915647 171402445 171402446 168889242 168889243 166376037 166376038 163862830 163862831 161349621 161349622 158836410 158836411 156323197 156323198 153809982 153809983 151296765 151296766 148783546 148783547 146270325 146270326 143757102 143757103 141243877 141243878 138730650 138730651 136217421 136217422 133704190 133704191 131190957 131190958 128677722 128677723 126164485 126164486 123651246 123651247 121138005 121138006 118624762 118624763 116111517 116111518 113598270 113598271 111085021 111085022 108571770 108571771 106058517 106058518 103545262 103545263 101032005 101032006 98518746 98518747 96005485 96005486 93492222 93492223 90978957 90978958 88465690 88465691 85952421 85952422 83439150 83439151 80925877 80925878 78412602 78412603 75899325 75899326 73386046 73386047 70872765 70872766 68359482 68359483 65846197 65846198 63332910 63332911 60819621 60819622 58306330 58306331 55793037 55793038 53279742 53279743 50766445 50766446 48253146 48253147 45739845 45739846 43226542 43226543 40713237 40713238 38199930 38199931 35686621 35686622 33173310 33173311 30659997 30659998 28146682 28146683 25633365 25633366 23120046 23120047 20606725 20606726 18093402 18093403 15580077 15580078 13066750 13066751 10553421 10553422 8040090 8040091 5526757 5526758 3013422 3013423 500085 500086 997986753 997986754 995473412 995473413 992960069 992960070 990446724 990446725 987933377 987933378 985420028 985420029 982906677 982906678 980393324 980393325 977879969 977879970 975366612 975366613 972853253 972853254 970339892 970339893 967826529 967826530 965313164 965313165 962799797 962799798 960286428 960286429 957773057 957773058 955259684 955259685 952746309 952746310 950232932 950232933 947719553 947719554 945206172 945206173 942692789 942692790 940179404 940179405 937666017 937666018 935152628 935152629 932639237 932639238 930125844 930125845 927612449 927612450 925099052 925099053 922585653 922585654 920072252 920072253 917558849 917558850 915045444 915045445 912532037 912532038 910018628 910018629 907505217 907505218 904991804 904991805 902478389 902478390 899964972 899964973 897451553 897451554 894938132 894938133 892424709 892424710 889911284 889911285 887397857 887397858 884884428 884884429 882370997 882370998 879857564 879857565 877344129 877344130 874830692 874830693 872317253 872317254 869803812 869803813 867290369 867290370 864776924 864776925 862263477 862263478 859750028 859750029 857236577 857236578 854723124 854723125 852209669 852209670 849696212 849696213 847182753 847182754 844669292 844669293 842155829 842155830 839642364 839642365 837128897 837128898 834615428 834615429 832101957 832101958 829588484 829588485 827075009 827075010 824561532 824561533 822048053 822048054 819534572 819534573 817021089 817021090 814507604 814507605 811994117 811994118 809480628 809480629 806967137 806967138 804453644 804453645 801940149 801940150 799426652 799426653 796913153 796913154 794399652 794399653 791886149 791886150 789372644 789372645 786859137 786859138 784345628 784345629 781832117 781832118 779318604 779318605 776805089 776805090 774291572 774291573 771778053 771778054 769264532 769264533 766751009 766751010 764237484 764237485 761723957 761723958 759210428 759210429 756696897 756696898 754183364 754183365 751669829 751669830 749156292 749156293 746642753 746642754 744129212 744129213 741615669 741615670 739102124 739102125 736588577 736588578 734075028 734075029 731561477 731561478 729047924 729047925 726534369 726534370 724020812 724020813 721507253 721507254 718993692 718993693 716480129 716480130 713966564 713966565 711452997 711452998 708939428 708939429 706425857 706425858 703912284 703912285 701398709 701398710 698885132 698885133 696371553 696371554 693857972 693857973 691344389 691344390 688830804 688830805 686317217 686317218 683803628 683803629 681290037 681290038 678776444 678776445 676262849 676262850 673749252 673749253 671235653 671235654 668722052 668722053 666208449 666208450 663694844 663694845 661181237 661181238 658667628 658667629 656154017 656154018 653640404 653640405 651126789 651126790 648613172 648613173 646099553 646099554 643585932 643585933 641072309 641072310 638558684 638558685 636045057 636045058 633531428 633531429 631017797 631017798 628504164 628504165 625990529 625990530 623476892 623476893 620963253 620963254 618449612 618449613 615935969 615935970 613422324 613422325 610908677 610908678 608395028 608395029 605881377 605881378 603367724 603367725 600854069 600854070 598340412 598340413 595826753 595826754 593313092 593313093 590799429 590799430 588285764 588285765 585772097 585772098 583258428 583258429 580744757 580744758 578231084 578231085 575717409 575717410 573203732 573203733 570690053 570690054 568176372 568176373 565662689 565662690 563149004 563149005 560635317 560635318 558121628 558121629 555607937 555607938 553094244 553094245 550580549 550580550 548066852 548066853 545553153 545553154 543039452 543039453 540525749 540525750 538012044 538012045 535498337 535498338 532984628 532984629 530470917 530470918 527957204 527957205 525443489 525443490 522929772 522929773 520416053 520416054 517902332 517902333 515388609 515388610 512874884 512874885 510361157 510361158 507847428 507847429 505333697 505333698 502819964 502819965 500306229 500306230 497792492 497792493 495278753 495278754 492765012 492765013 490251269 490251270 487737524 487737525 485223777 485223778 482710028 482710029 480196277 480196278 477682524 477682525 475168769 475168770 472655012 472655013 470141253 470141254 467627492 467627493 465113729 465113730 462599964 462599965 460086197 460086198 457572428 457572429 455058657 455058658 452544884 452544885 450031109 450031110 447517332 447517333 445003553 445003554 442489772 442489773 439975989 439975990 437462204 437462205 434948417 434948418 432434628 432434629 429920837 429920838 427407044 427407045 424893249 424893250 422379452 422379453 419865653 419865654 417351852 417351853 414838049 414838050 412324244 412324245 409810437 409810438 407296628 407296629 404782817 404782818 402269004 402269005 399755189 399755190 397241372 397241373 394727553 394727554 392213732 392213733 389699909 389699910 387186084 387186085 384672257 384672258 382158428 382158429 379644597 379644598 377130764 377130765 374616929 374616930 372103092 372103093 369589253 369589254 367075412 367075413 364561569 364561570 362047724 362047725 359533877 359533878 357020028 357020029 354506177 354506178 351992324 351992325 349478469 349478470 346964612 346964613 344450753 344450754 341936892 341936893 339423029 339423030 336909164 336909165 334395297 334395298 331881428 331881429 329367557 329367558 326853684 326853685 324339809 324339810 321825932 321825933 319312053 319312054 316798172 316798173 314284289 314284290 311770404 311770405 309256517 309256518 306742628 306742629 304228737 304228738 301714844 301714845 299200949 299200950 296687052 296687053 294173153 294173154 291659252 291659253 289145349 289145350 286631444 286631445 284117537 284117538 281603628 281603629 279089717 279089718 276575804 276575805 274061889 274061890 271547972 271547973 269034053 269034054 266520132 266520133 264006209 264006210 261492284 261492285 258978357 258978358 256464428 256464429 253950497 253950498 251436564 251436565 248922629 248922630 246408692 246408693 243894753 243894754 241380812 241380813 238866869 238866870 236352924 236352925 233838977 233838978 231325028 231325029 228811077 228811078 226297124 226297125 223783169 223783170 221269212 221269213 218755253 218755254 216241292 216241293 213727329 213727330 211213364 211213365 208699397 208699398 206185428 206185429 203671457 203671458 201157484 201157485 198643509 198643510 196129532 196129533 193615553 193615554 191101572 191101573 188587589 188587590 186073604 186073605 183559617 183559618 181045628 181045629 178531637 178531638 176017644 176017645 173503649 173503650 170989652 170989653 168475653 168475654 165961652 165961653 163447649 163447650 160933644 160933645 158419637 158419638 155905628 155905629 153391617 153391618 150877604 150877605 148363589 148363590 145849572 145849573 143335553 143335554 140821532 140821533 138307509 138307510 135793484 135793485 133279457 133279458 130765428 130765429 128251397 128251398 125737364 125737365 123223329 123223330 120709292 120709293 118195253 118195254 115681212 115681213 113167169 113167170 110653124 110653125 108139077 108139078 105625028 105625029 103110977 103110978 100596924 100596925 98082869 98082870 95568812 95568813 93054753 93054754 90540692 90540693 88026629 88026630 85512564 85512565 82998497 82998498 80484428 80484429 77970357 77970358 75456284 75456285 72942209 72942210 70428132 70428133 67914053 67914054 65399972 65399973 62885889 62885890 60371804 60371805 57857717 57857718 55343628 55343629 52829537 52829538 50315444 50315445 47801349 47801350 45287252 45287253 42773153 42773154 40259052 40259053 37744949 37744950 35230844 35230845 32716737 32716738 30202628 30202629 27688517 27688518 25174404 25174405 22660289 22660290 20146172 20146173 17632053 17632054 15117932 15117933 12603809 12603810 10089684 10089685 7575557 7575558 5061428 5061429 2547297 2547298 33164 33165 997519036 997519037 995004899 995004900 992490760 992490761 989976619 989976620 987462476 987462477 984948331 984948332 982434184 982434185 979920035 979920036 977405884 977405885 974891731 974891732 972377576 972377577 969863419 969863420 967349260 967349261 964835099 964835100 962320936 962320937 959806771 959806772 957292604 957292605 954778435 954778436 952264264 952264265 949750091 949750092 947235916 947235917 944721739 944721740 942207560 942207561 939693379 939693380 937179196 937179197 934665011 934665012 932150824 932150825 929636635 929636636 927122444 927122445 924608251 924608252 922094056 922094057 919579859 919579860 917065660 917065661 914551459 914551460 912037256 912037257 909523051 909523052 907008844 907008845 904494635 904494636 901980424 901980425 899466211 899466212 896951996 896951997 894437779 894437780 891923560 891923561 889409339 889409340 886895116 886895117 884380891 884380892 881866664 881866665 879352435 879352436 876838204 876838205 874323971 874323972 871809736 871809737 869295499 869295500 866781260 866781261 864267019 864267020 861752776 861752777 859238531 859238532 856724284 856724285 854210035 854210036 851695784 851695785 849181531 849181532 846667276 846667277 844153019 844153020 841638760 841638761 839124499 839124500 836610236 836610237 834095971 834095972 831581704 831581705 829067435 829067436 826553164 826553165 824038891 824038892 821524616 821524617 819010339 819010340 816496060 816496061 813981779 813981780 811467496 811467497 808953211 808953212 806438924 806438925 803924635 803924636 801410344 801410345 798896051 798896052 796381756 796381757 793867459 793867460 791353160 791353161 788838859 788838860 786324556 786324557 783810251 783810252 781295944 781295945 778781635 778781636 776267324 776267325 773753011 773753012 771238696 771238697 768724379 768724380 766210060 766210061 763695739 763695740 761181416 761181417 758667091 758667092 756152764 756152765 753638435 753638436 751124104 751124105 748609771 748609772 746095436 746095437 743581099 743581100 741066760 741066761 738552419 738552420 736038076 736038077 733523731 733523732 731009384 731009385 728495035 728495036 725980684 725980685 723466331 723466332 720951976 720951977 718437619 718437620 715923260 715923261 713408899 713408900 710894536 710894537 708380171 708380172 705865804 705865805 703351435 703351436 700837064 700837065 698322691 698322692 695808316 695808317 693293939 693293940 690779560 690779561 688265179 688265180 685750796 685750797 683236411 683236412 680722024 680722025 678207635 678207636 675693244 675693245 673178851 673178852 670664456 670664457 668150059 668150060 665635660 665635661 663121259 663121260 660606856 660606857 658092451 658092452 655578044 655578045 653063635 653063636 650549224 650549225 648034811 648034812 645520396 645520397 643005979 643005980 640491560 640491561 637977139 637977140 635462716 635462717 632948291 632948292 630433864 630433865 627919435 627919436 625405004 625405005 622890571 622890572 620376136 620376137 617861699 617861700 615347260 615347261 612832819 612832820 610318376 610318377 607803931 607803932 605289484 605289485 602775035 602775036 600260584 600260585 597746131 597746132 595231676 595231677 592717219 592717220 590202760 590202761 587688299 587688300 585173836 585173837 582659371 582659372 580144904 580144905 577630435 577630436 575115964 575115965 572601491 572601492 570087016 570087017 567572539 567572540 565058060 565058061 562543579 562543580 560029096 560029097 557514611 557514612 555000124 555000125 552485635 552485636 549971144 549971145 547456651 547456652 544942156 544942157 542427659 542427660 539913160 539913161 537398659 537398660 534884156 534884157 532369651 532369652 529855144 529855145 527340635 527340636 524826124 524826125 522311611 522311612 519797096 519797097 517282579 517282580 514768060 514768061 512253539 512253540 509739016 509739017 507224491 507224492 504709964 504709965 502195435 502195436 499680904 499680905 497166371 497166372 494651836 494651837 492137299 492137300 489622760 489622761 487108219 487108220 484593676 484593677 482079131 482079132 479564584 479564585 477050035 477050036 474535484 474535485 472020931 472020932 469506376 469506377 466991819 466991820 464477260 464477261 461962699 461962700 459448136 459448137 456933571 456933572 454419004 454419005 451904435 451904436 449389864 449389865 446875291 446875292 444360716 444360717 441846139 441846140 439331560 439331561 436816979 436816980 434302396 434302397 431787811 431787812 429273224 429273225 426758635 426758636 424244044 424244045 421729451 421729452 419214856 419214857 416700259 416700260 414185660 414185661 411671059 411671060 409156456 409156457 406641851 406641852 404127244 404127245 401612635 401612636 399098024 399098025 396583411 396583412 394068796 394068797 391554179 391554180 389039560 389039561 386524939 386524940 384010316 384010317 381495691 381495692 378981064 378981065 376466435 376466436 373951804 373951805 371437171 371437172 368922536 368922537 366407899 366407900 363893260 363893261 361378619 361378620 358863976 358863977 356349331 356349332 353834684 353834685 351320035 351320036 348805384 348805385 346290731 346290732 343776076 343776077 341261419 341261420 338746760 338746761 336232099 336232100 333717436 333717437 331202771 331202772 328688104 328688105 326173435 326173436 323658764 323658765 321144091 321144092 318629416 318629417 316114739 316114740 313600060 313600061 311085379 311085380 308570696 308570697 306056011 306056012 303541324 303541325 301026635 301026636 298511944 298511945 295997251 295997252 293482556 293482557 290967859 290967860 288453160 288453161 285938459 285938460 283423756 283423757 280909051 280909052 278394344 278394345 275879635 275879636 273364924 273364925 270850211 270850212 268335496 268335497 265820779 265820780 263306060 263306061 260791339 260791340 258276616 258276617 255761891 255761892 253247164 253247165 250732435 250732436 248217704 248217705 245702971 245702972 243188236 243188237 240673499 240673500 238158760 238158761 235644019 235644020 233129276 233129277 230614531 230614532 228099784 228099785 225585035 225585036 223070284 223070285 220555531 220555532 218040776 218040777 215526019 215526020 213011260 213011261 210496499 210496500 207981736 207981737 205466971 205466972 202952204 202952205 200437435 200437436 197922664 197922665 195407891 195407892 192893116 192893117 190378339 190378340 187863560 187863561 185348779 185348780 182833996 182833997 180319211 180319212 177804424 177804425 175289635 175289636 172774844 172774845 170260051 170260052 167745256 167745257 165230459 165230460 162715660 162715661 160200859 160200860 157686056 157686057 155171251 155171252 152656444 152656445 150141635 150141636 147626824 147626825 145112011 145112012 142597196 142597197 140082379 140082380 137567560 137567561 135052739 135052740 132537916 132537917 130023091 130023092 127508264 127508265 124993435 124993436 122478604 122478605 119963771 119963772 117448936 117448937 114934099 114934100 112419260 112419261 109904419 109904420 107389576 107389577 104874731 104874732 102359884 102359885 99845035 99845036 97330184 97330185 94815331 94815332 92300476 92300477 89785619 89785620 87270760 87270761 84755899 84755900 82241036 82241037 79726171 79726172 77211304 77211305 74696435 74696436 72181564 72181565 69666691 69666692 67151816 67151817 64636939 64636940 62122060 62122061 59607179 59607180 57092296 57092297 54577411 54577412 52062524 52062525 49547635 49547636 47032744 47032745 44517851 44517852 42002956 42002957 39488059 39488060 36973160 36973161 34458259 34458260 31943356 31943357 29428451 29428452 26913544 26913545 24398635 24398636 21883724 21883725 19368811 19368812 16853896 16853897 14338979 14338980 11824060 11824061 9309139 9309140 6794216 6794217 4279291 4279292 1764364 1764365 999249442 999249443 996734511 996734512 994219578 994219579 991704643 991704644 989189706 989189707 986674767 986674768 984159826 984159827 981644883 981644884 979129938 979129939 976614991 976614992 974100042 974100043 971585091 971585092 969070138 969070139 966555183 966555184 964040226 964040227 961525267 961525268 959010306 959010307 956495343 956495344 953980378 953980379 951465411 951465412 948950442 948950443 946435471 946435472 943920498 943920499 941405523 941405524 938890546 938890547 936375567 936375568 933860586 933860587 931345603 931345604 928830618 928830619 926315631 926315632 923800642 923800643 921285651 921285652 918770658 918770659 916255663 916255664 913740666 913740667 911225667 911225668 908710666 908710667 906195663 906195664 903680658 903680659 901165651 901165652 898650642 898650643 896135631 896135632 893620618 893620619 891105603 891105604 888590586 888590587 886075567 886075568 883560546 883560547 881045523 881045524 878530498 878530499 876015471 876015472 873500442 873500443 870985411 870985412 868470378 868470379 865955343 865955344 863440306 863440307 860925267 860925268 858410226 858410227 855895183 855895184 853380138 853380139 850865091 850865092 848350042 848350043 845834991 845834992 843319938 843319939 840804883 840804884 838289826 838289827 835774767 835774768 833259706 833259707 830744643 830744644 828229578 828229579 825714511 825714512 823199442 823199443 820684371 820684372 818169298 818169299 815654223 815654224 813139146 813139147 810624067 810624068 808108986 808108987 805593903 805593904 803078818 803078819 800563731 800563732 798048642 798048643 795533551 795533552 793018458 793018459 790503363 790503364 787988266 787988267 785473167 785473168 782958066 782958067 780442963 780442964 777927858 777927859 775412751 775412752 772897642 772897643 770382531 770382532 767867418 767867419 765352303 765352304 762837186 762837187 760322067 760322068 757806946 757806947 755291823 755291824 752776698 752776699 750261571 750261572 747746442 747746443 745231311 745231312 742716178 742716179 740201043 740201044 737685906 737685907 735170767 735170768 732655626 732655627 730140483 730140484 727625338 727625339 725110191 725110192 722595042 722595043 720079891 720079892 717564738 717564739 715049583 715049584 712534426 712534427 710019267 710019268 707504106 707504107 704988943 704988944 702473778 702473779 699958611 699958612 697443442 697443443 694928271 694928272 692413098 692413099 689897923 689897924 687382746 687382747 684867567 684867568 682352386 682352387 679837203 679837204 677322018 677322019 674806831 674806832 672291642 672291643 669776451 669776452 667261258 667261259 664746063 664746064 662230866 662230867 659715667 659715668 657200466 657200467 654685263 654685264 652170058 652170059 649654851 649654852 647139642 647139643 644624431 644624432 642109218 642109219 639594003 639594004 637078786 637078787 634563567 634563568 632048346 632048347 629533123 629533124 627017898 627017899 624502671 624502672 621987442 621987443 619472211 619472212 616956978 616956979 614441743 614441744 611926506 611926507 609411267 609411268 606896026 606896027 604380783 604380784 601865538 601865539 599350291 599350292 596835042 596835043 594319791 594319792 591804538 591804539 589289283 589289284 586774026 586774027 584258767 584258768 581743506 581743507 579228243 579228244 576712978 576712979 574197711 574197712 571682442 571682443 569167171 569167172 566651898 566651899 564136623 564136624 561621346 561621347 559106067 559106068 556590786 556590787 554075503 554075504 551560218 551560219 549044931 549044932 546529642 546529643 544014351 544014352 541499058 541499059 538983763 538983764 536468466 536468467 533953167 533953168 531437866 531437867 528922563 528922564 526407258 526407259 523891951 523891952 521376642 521376643 518861331 518861332 516346018 516346019 513830703 513830704 511315386 511315387 508800067 508800068 506284746 506284747 503769423 503769424 501254098 501254099 498738771 498738772 496223442 496223443 493708111 493708112 491192778 491192779 488677443 488677444 486162106 486162107 483646767 483646768 481131426 481131427 478616083 478616084 476100738 476100739 473585391 473585392 471070042 471070043 468554691 468554692 466039338 466039339 463523983 463523984 461008626 461008627 458493267 458493268 455977906 455977907 453462543 453462544 450947178 450947179 448431811 448431812 445916442 445916443 443401071 443401072 440885698 440885699 438370323 438370324 435854946 435854947 433339567 433339568 430824186 430824187 428308803 428308804 425793418 425793419 423278031 423278032 420762642 420762643 418247251 418247252 415731858 415731859 413216463 413216464 410701066 410701067 408185667 408185668 405670266 405670267 403154863 403154864 400639458 400639459 398124051 398124052 395608642 395608643 393093231 393093232 390577818 390577819 388062403 388062404 385546986 385546987 383031567 383031568 380516146 380516147 378000723 378000724 375485298 375485299 372969871 372969872 370454442 370454443 367939011 367939012 365423578 365423579 362908143 362908144 360392706 360392707 357877267 357877268 355361826 355361827 352846383 352846384 350330938 350330939 347815491 347815492 345300042 345300043 342784591 342784592 340269138 340269139 337753683 337753684 335238226 335238227 332722767 332722768 330207306 330207307 327691843 327691844 325176378 325176379 322660911 322660912 320145442 320145443 317629971 317629972 315114498 315114499 312599023 312599024 310083546 310083547 307568067 307568068 305052586 305052587 302537103 302537104 300021618 300021619 297506131 297506132 294990642 294990643 292475151 292475152 289959658 289959659 287444163 287444164 284928666 284928667 282413167 282413168 279897666 279897667 277382163 277382164 274866658 274866659 272351151 272351152 269835642 269835643 267320131 267320132 264804618 264804619 262289103 262289104 259773586 259773587 257258067 257258068 254742546 254742547 252227023 252227024 249711498 249711499 247195971 247195972 244680442 244680443 242164911 242164912 239649378 239649379 237133843 237133844 234618306 234618307 232102767 232102768 229587226 229587227 227071683 227071684 224556138 224556139 222040591 222040592 219525042 219525043 217009491 217009492 214493938 214493939 211978383 211978384 209462826 209462827 206947267 206947268 204431706 204431707 201916143 201916144 199400578 199400579 196885011 196885012 194369442 194369443 191853871 191853872 189338298 189338299 186822723 186822724 184307146 184307147 181791567 181791568 179275986 179275987 176760403 176760404 174244818 174244819 171729231 171729232 169213642 169213643 166698051 166698052 164182458 164182459 161666863 161666864 159151266 159151267 156635667 156635668 154120066 154120067 151604463 151604464 149088858 149088859 146573251 146573252 144057642 144057643 141542031 141542032 139026418 139026419 136510803 136510804 133995186 133995187 131479567 131479568 128963946 128963947 126448323 126448324 123932698 123932699 121417071 121417072 118901442 118901443 116385811 116385812 113870178 113870179 111354543 111354544 108838906 108838907 106323267 106323268 103807626 103807627 101291983 101291984 98776338 98776339 96260691 96260692 93745042 93745043 91229391 91229392 88713738 88713739 86198083 86198084 83682426 83682427 81166767 81166768 78651106 78651107 76135443 76135444 73619778 73619779 71104111 71104112 68588442 68588443 66072771 66072772 63557098 63557099 61041423 61041424 58525746 58525747 56010067 56010068 53494386 53494387 50978703 50978704 48463018 48463019 45947331 45947332 43431642 43431643 40915951 40915952 38400258 38400259 35884563 35884564 33368866 33368867 30853167 30853168 28337466 28337467 25821763 25821764 23306058 23306059 20790351 20790352 18274642 18274643 15758931 15758932 13243218 13243219 10727503 10727504 8211786 8211787 5696067 5696068 3180346 3180347 664623 664624 998148905 998148906 995633178 995633179 993117449 993117450 990601718 990601719 988085985 988085986 985570250 985570251 983054513 983054514 980538774 980538775 978023033 978023034 975507290 975507291 972991545 972991546 970475798 970475799 967960049 967960050 965444298 965444299 962928545 962928546 960412790 960412791 957897033 957897034 955381274 955381275 952865513 952865514 950349750 950349751 947833985 947833986 945318218 945318219 942802449 942802450 940286678 940286679 937770905 937770906 935255130 935255131 932739353 932739354 930223574 930223575 927707793 927707794 925192010 925192011 922676225 922676226 920160438 920160439 917644649 917644650 915128858 915128859 912613065 912613066 910097270 910097271 907581473 907581474 905065674 905065675 902549873 902549874 900034070 900034071 897518265 897518266 895002458 895002459 892486649 892486650 889970838 889970839 887455025 887455026 884939210 884939211 882423393 882423394 879907574 879907575 877391753 877391754 874875930 874875931 872360105 872360106 869844278 869844279 867328449 867328450 864812618 864812619 862296785 862296786 859780950 859780951 857265113 857265114 854749274 854749275 852233433 852233434 849717590 849717591 847201745 847201746 844685898 844685899 842170049 842170050 839654198 839654199 837138345 837138346 834622490 834622491 832106633 832106634 829590774 829590775 827074913 827074914 824559050 824559051 822043185 822043186 819527318 819527319 817011449 817011450 814495578 814495579 811979705 811979706 809463830 809463831 806947953 806947954 804432074 804432075 801916193 801916194 799400310 799400311 796884425 796884426 794368538 794368539 791852649 791852650 789336758 789336759 786820865 786820866 784304970 784304971 781789073 781789074 779273174 779273175 776757273 776757274 774241370 774241371 771725465 771725466 769209558 769209559 766693649 766693650 764177738 764177739 761661825 761661826 759145910 759145911 756629993 756629994 754114074 754114075 751598153 751598154 749082230 749082231 746566305 746566306 744050378 744050379 741534449 741534450 739018518 739018519 736502585 736502586 733986650 733986651 731470713 731470714 728954774 728954775 726438833 726438834 723922890 723922891 721406945 721406946 718890998 718890999 716375049 716375050 713859098 713859099 711343145 711343146 708827190 708827191 706311233 706311234 703795274 703795275 701279313 701279314 698763350 698763351 696247385 696247386 693731418 693731419 691215449 691215450 688699478 688699479 686183505 686183506 683667530 683667531 681151553 681151554 678635574 678635575 676119593 676119594 673603610 673603611 671087625 671087626 668571638 668571639 666055649 666055650 663539658 663539659 661023665 661023666 658507670 658507671 655991673 655991674 653475674 653475675 650959673 650959674 648443670 648443671 645927665 645927666 643411658 643411659 640895649 640895650 638379638 638379639 635863625 635863626 633347610 633347611 630831593 630831594 628315574 628315575 625799553 625799554 623283530 623283531 620767505 620767506 618251478 618251479 615735449 615735450 613219418 613219419 610703385 610703386 608187350 608187351 605671313 605671314 603155274 603155275 600639233 600639234 598123190 598123191 595607145 595607146 593091098 593091099 590575049 590575050 588058998 588058999 585542945 585542946 583026890 583026891 580510833 580510834 577994774 577994775 575478713 575478714 572962650 572962651 570446585 570446586 567930518 567930519 565414449 565414450 562898378 562898379 560382305 560382306 557866230 557866231 555350153 555350154 552834074 552834075 550317993 550317994 547801910 547801911 545285825 545285826 542769738 542769739 540253649 540253650 537737558 537737559 535221465 535221466 532705370 532705371 530189273 530189274 527673174 527673175 525157073 525157074 522640970 522640971 520124865 520124866 517608758 517608759 515092649 515092650 512576538 512576539 510060425 510060426 507544310 507544311 505028193 505028194 502512074 502512075 499995953 499995954 497479830 497479831 494963705 494963706 492447578 492447579 489931449 489931450 487415318 487415319 484899185 484899186 482383050 482383051 479866913 479866914 477350774 477350775 474834633 474834634 472318490 472318491 469802345 469802346 467286198 467286199 464770049 464770050 462253898 462253899 459737745 459737746 457221590 457221591 454705433 454705434 452189274 452189275 449673113 449673114 447156950 447156951 444640785 444640786 442124618 442124619 439608449 439608450 437092278 437092279 434576105 434576106 432059930 432059931 429543753 429543754 427027574 427027575 424511393 424511394 421995210 421995211 419479025 419479026 416962838 416962839 414446649 414446650 411930458 411930459 409414265 409414266 406898070 406898071 404381873 404381874 401865674 401865675 399349473 399349474 396833270 396833271 394317065 394317066 391800858 391800859 389284649 389284650 386768438 386768439 384252225 384252226 381736010 381736011 379219793 379219794 376703574 376703575 374187353 374187354 371671130 371671131 369154905 369154906 366638678 366638679 364122449 364122450 361606218 361606219 359089985 359089986 356573750 356573751 354057513 354057514 351541274 351541275 349025033 349025034 346508790 346508791 343992545 343992546 341476298 341476299 338960049 338960050 336443798 336443799 333927545 333927546 331411290 331411291 328895033 328895034 326378774 326378775 323862513 323862514 321346250 321346251 318829985 318829986 316313718 316313719 313797449 313797450 311281178 311281179 308764905 308764906 306248630 306248631 303732353 303732354 301216074 301216075 298699793 298699794 296183510 296183511 293667225 293667226 291150938 291150939 288634649 288634650 286118358 286118359 283602065 283602066 281085770 281085771 278569473 278569474 276053174 276053175 273536873 273536874 271020570 271020571 268504265 268504266 265987958 265987959 263471649 263471650 260955338 260955339 258439025 258439026 255922710 255922711 253406393 253406394 250890074 250890075 248373753 248373754 245857430 245857431 243341105 243341106 240824778 240824779 238308449 238308450 235792118 235792119 233275785 233275786 230759450 230759451 228243113 228243114 225726774 225726775 223210433 223210434 220694090 220694091 218177745 218177746 215661398 215661399 213145049 213145050 210628698 210628699 208112345 208112346 205595990 205595991 203079633 203079634 200563274 200563275 198046913 198046914 195530550 195530551 193014185 193014186 190497818 190497819 187981449 187981450 185465078 185465079 182948705 182948706 180432330 180432331 177915953 177915954 175399574 175399575 172883193 172883194 170366810 170366811 167850425 167850426 165334038 165334039 162817649 162817650 160301258 160301259 157784865 157784866 155268470 155268471 152752073 152752074 150235674 150235675 147719273 147719274 145202870 145202871 142686465 142686466 140170058 140170059 137653649 137653650 135137238 135137239 132620825 132620826 130104410 130104411 127587993 127587994 125071574 125071575 122555153 122555154 120038730 120038731 117522305 117522306 115005878 115005879 112489449 112489450 109973018 109973019 107456585 107456586 104940150 104940151 102423713 102423714 99907274 99907275 97390833 97390834 94874390 94874391 92357945 92357946 89841498 89841499 87325049 87325050 84808598 84808599 82292145 82292146 79775690 79775691 77259233 77259234 74742774 74742775 72226313 72226314 69709850 69709851 67193385 67193386 64676918 64676919 62160449 62160450 59643978 59643979 57127505 57127506 54611030 54611031 52094553 52094554 49578074 49578075 47061593 47061594 44545110 44545111 42028625 42028626 39512138 39512139 36995649 36995650 34479158 34479159 31962665 31962666 29446170 29446171 26929673 26929674 24413174 24413175 21896673 21896674 19380170 19380171 16863665 16863666 14347158 14347159 11830649 11830650 9314138 9314139 6797625 6797626 4281110 4281111 1764593 1764594 999248081 999248082 996731560 996731561 994215037 994215038 991698512 991698513 989181985 989181986 986665456 986665457 984148925 984148926 981632392 981632393 979115857 979115858 976599320 976599321 974082781 974082782 971566240 971566241 969049697 969049698 966533152 966533153 964016605 964016606 961500056 961500057 958983505 958983506 956466952 956466953 953950397 953950398 951433840 951433841 948917281 948917282 946400720 946400721 943884157 943884158 941367592 941367593 938851025 938851026 936334456 936334457 933817885 933817886 931301312 931301313 928784737 928784738 926268160 926268161 923751581 923751582 921235000 921235001 918718417 918718418 916201832 916201833 913685245 913685246 911168656 911168657 908652065 908652066 906135472 906135473 903618877 903618878 901102280 901102281 898585681 898585682 896069080 896069081 893552477 893552478 891035872 891035873 888519265 888519266 886002656 886002657 883486045 883486046 880969432 880969433 878452817 878452818 875936200 875936201 873419581 873419582 870902960 870902961 868386337 868386338 865869712 865869713 863353085 863353086 860836456 860836457 858319825 858319826 855803192 855803193 853286557 853286558 850769920 850769921 848253281 848253282 845736640 845736641 843219997 843219998 840703352 840703353 838186705 838186706 835670056 835670057 833153405 833153406 830636752 830636753 828120097 828120098 825603440 825603441 823086781 823086782 820570120 820570121 818053457 818053458 815536792 815536793 813020125 813020126 810503456 810503457 807986785 807986786 805470112 805470113 802953437 802953438 800436760 800436761 797920081 797920082 795403400 795403401 792886717 792886718 790370032 790370033 787853345 787853346 785336656 785336657 782819965 782819966 780303272 780303273 777786577 777786578 775269880 775269881 772753181 772753182 770236480 770236481 767719777 767719778 765203072 765203073 762686365 762686366 760169656 760169657 757652945 757652946 755136232 755136233 752619517 752619518 750102800 750102801 747586081 747586082 745069360 745069361 742552637 742552638 740035912 740035913 737519185 737519186 735002456 735002457 732485725 732485726 729968992 729968993 727452257 727452258 724935520 724935521 722418781 722418782 719902040 719902041 717385297 717385298 714868552 714868553 712351805 712351806 709835056 709835057 707318305 707318306 704801552 704801553 702284797 702284798 699768040 699768041 697251281 697251282 694734520 694734521 692217757 692217758 689700992 689700993 687184225 687184226 684667456 684667457 682150685 682150686 679633912 679633913 677117137 677117138 674600360 674600361 672083581 672083582 669566800 669566801 667050017 667050018 664533232 664533233 662016445 662016446 659499656 659499657 656982865 656982866 654466072 654466073 651949277 651949278 649432480 649432481 646915681 646915682 644398880 644398881 641882077 641882078 639365272 639365273 636848465 636848466 634331656 634331657 631814845 631814846 629298032 629298033 626781217 626781218 624264400 624264401 621747581 621747582 619230760 619230761 616713937 616713938 614197112 614197113 611680285 611680286 609163456 609163457 606646625 606646626 604129792 604129793 601612957 601612958 599096120 599096121 596579281 596579282 594062440 594062441 591545597 591545598 589028752 589028753 586511905 586511906 583995056 583995057 581478205 581478206 578961352 578961353 576444497 576444498 573927640 573927641 571410781 571410782 568893920 568893921 566377057 566377058 563860192 563860193 561343325 561343326 558826456 558826457 556309585 556309586 553792712 553792713 551275837 551275838 548758960 548758961 546242081 546242082 543725200 543725201 541208317 541208318 538691432 538691433 536174545 536174546 533657656 533657657 531140765 531140766 528623872 528623873 526106977 526106978 523590080 523590081 521073181 521073182 518556280 518556281 516039377 516039378 513522472 513522473 511005565 511005566 508488656 508488657 505971745 505971746 503454832 503454833 500937917 500937918 498421000 498421001 495904081 495904082 493387160 493387161 490870237 490870238 488353312 488353313 485836385 485836386 483319456 483319457 480802525 480802526 478285592 478285593 475768657 475768658 473251720 473251721 470734781 470734782 468217840 468217841 465700897 465700898 463183952 463183953 460667005 460667006 458150056 458150057 455633105 455633106 453116152 453116153 450599197 450599198 448082240 448082241 445565281 445565282 443048320 443048321 440531357 440531358 438014392 438014393 435497425 435497426 432980456 432980457 430463485 430463486 427946512 427946513 425429537 425429538 422912560 422912561 420395581 420395582 417878600 417878601 415361617 415361618 412844632 412844633 410327645 410327646 407810656 407810657 405293665 405293666 402776672 402776673 400259677 400259678 397742680 397742681 395225681 395225682 392708680 392708681 390191677 390191678 387674672 387674673 385157665 385157666 382640656 382640657 380123645 380123646 377606632 377606633 375089617 375089618 372572600 372572601 370055581 370055582 367538560 367538561 365021537 365021538 362504512 362504513 359987485 359987486 357470456 357470457 354953425 354953426 352436392 352436393 349919357 349919358 347402320 347402321 344885281 344885282 342368240 342368241 339851197 339851198 337334152 337334153 334817105 334817106 332300056 332300057 329783005 329783006 327265952 327265953 324748897 324748898 322231840 322231841 319714781 319714782 317197720 317197721 314680657 314680658 312163592 312163593 309646525 309646526 307129456 307129457 304612385 304612386 302095312 302095313 299578237 299578238 297061160 297061161 294544081 294544082 292027000 292027001 289509917 289509918 286992832 286992833 284475745 284475746 281958656 281958657 279441565 279441566 276924472 276924473 274407377 274407378 271890280 271890281 269373181 269373182 266856080 266856081 264338977 264338978 261821872 261821873 259304765 259304766 256787656 256787657 254270545 254270546 251753432 251753433 249236317 249236318 246719200 246719201 244202081 244202082 241684960 241684961 239167837 239167838 236650712 236650713 234133585 234133586 231616456 231616457 229099325 229099326 226582192 226582193 224065057 224065058 221547920 221547921 219030781 219030782 216513640 216513641 213996497 213996498 211479352 211479353 208962205 208962206 206445056 206445057 203927905 203927906 201410752 201410753 198893597 198893598 196376440 196376441 193859281 193859282 191342120 191342121 188824957 188824958 186307792 186307793 183790625 183790626 181273456 181273457 178756285 178756286 176239112 176239113 173721937 173721938 171204760 171204761 168687581 168687582 166170400 166170401 163653217 163653218 161136032 161136033 158618845 158618846 156101656 156101657 153584465 153584466 151067272 151067273 148550077 148550078 146032880 146032881 143515681 143515682 140998480 140998481 138481277 138481278 135964072 135964073 133446865 133446866 130929656 130929657 128412445 128412446 125895232 125895233 123378017 123378018 120860800 120860801 118343581 118343582 115826360 115826361 113309137 113309138 110791912 110791913 108274685 108274686 105757456 105757457 103240225 103240226 100722992 100722993 98205757 98205758 95688520 95688521 93171281 93171282 90654040 90654041 88136797 88136798 85619552 85619553 83102305 83102306 80585056 80585057 78067805 78067806 75550552 75550553 73033297 73033298 70516040 70516041 67998781 67998782 65481520 65481521 62964257 62964258 60446992 60446993 57929725 57929726 55412456 55412457 52895185 52895186 50377912 50377913 47860637 47860638 45343360 45343361 42826081 42826082 40308800 40308801 37791517 37791518 35274232 35274233 32756945 32756946 30239656 30239657 27722365 27722366 25205072 25205073 22687777 22687778 20170480 20170481 17653181 17653182 15135880 15135881 12618577 12618578 10101272 10101273 7583965 7583966 5066656 5066657 2549345 2549346 32032 32033 997514724 997514725 994997407 994997408 992480088 992480089 989962767 989962768 987445444 987445445 984928119 984928120 982410792 982410793 979893463 979893464 977376132 977376133 974858799 974858800 972341464 972341465 969824127 969824128 967306788 967306789 964789447 964789448 962272104 962272105 959754759 959754760 957237412 957237413 954720063 954720064 952202712 952202713 949685359 949685360 947168004 947168005 944650647 944650648 942133288 942133289 939615927 939615928 937098564 937098565 934581199 934581200 932063832 932063833 929546463 929546464 927029092 927029093 924511719 924511720 921994344 921994345 919476967 919476968 916959588 916959589 914442207 914442208 911924824 911924825 909407439 909407440 906890052 906890053 904372663 904372664 901855272 901855273 899337879 899337880 896820484 896820485 894303087 894303088 891785688 891785689 889268287 889268288 886750884 886750885 884233479 884233480 881716072 881716073 879198663 879198664 876681252 876681253 874163839 874163840 871646424 871646425 869129007 869129008 866611588 866611589 864094167 864094168 861576744 861576745 859059319 859059320 856541892 856541893 854024463 854024464 851507032 851507033 848989599 848989600 846472164 846472165 843954727 843954728 841437288 841437289 838919847 838919848 836402404 836402405 833884959 833884960 831367512 831367513 828850063 828850064 826332612 826332613 823815159 823815160 821297704 821297705 818780247 818780248 816262788 816262789 813745327 813745328 811227864 811227865 808710399 808710400 806192932 806192933 803675463 803675464 801157992 801157993 798640519 798640520 796123044 796123045 793605567 793605568 791088088 791088089 788570607 788570608 786053124 786053125 783535639 783535640 781018152 781018153 778500663 778500664 775983172 775983173 773465679 773465680 770948184 770948185 768430687 768430688 765913188 765913189 763395687 763395688 760878184 760878185 758360679 758360680 755843172 755843173 753325663 753325664 750808152 750808153 748290639 748290640 745773124 745773125 743255607 743255608 740738088 740738089 738220567 738220568 735703044 735703045 733185519 733185520 730667992 730667993 728150463 728150464 725632932 725632933 723115399 723115400 720597864 720597865 718080327 718080328 715562788 715562789 713045247 713045248 710527704 710527705 708010159 708010160 705492612 705492613 702975063 702975064 700457512 700457513 697939959 697939960 695422404 695422405 692904847 692904848 690387288 690387289 687869727 687869728 685352164 685352165 682834599 682834600 680317032 680317033 677799463 677799464 675281892 675281893 672764319 672764320 670246744 670246