Select solution language
Write solution here.
Nháºn thấy n <= 1e9, nên chúng ta là m mảng hằng
Code mẫu:
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int a[2000] = {510730514, 20624192, 858508365, 715336175, 353457261, 704383451, 878602023, 753815739, 445880403, 887508669,
170272986, 335423488, 694854500, 383709750, 155684157, 304485998, 988012348, 968253084, 300451810, 592236608, 222412840,
435257241, 947191645, 883907495, 681050781, 350712594, 266180755, 520053650, 186585680, 359938973, 964046492, 913930533,
318588669, 622079405, 917142271, 818245779, 917337251, 817689680, 97729481, 177522950, 58201727, 97511205, 679852547, 339851659,
446682252, 872545053, 541158523, 60526819, 495090603, 967415569, 582862985, 141980359, 579545007, 134359984, 960622296, 895525789,
772888521, 519065210, 928694722, 829680425, 933467720, 838225174, 316711956, 603708444, 948936694, 867148840, 575859597, 119981807,
884748425, 736742956, 528390332, 23006693, 522378687, 9959854, 786391699, 536958955, 347496208, 658137781, 644798788, 251709557, 618062831,
197201186, 674315346, 308666777, 441970125, 842934019, 142195128, 242338916, 148455114, 253811091, 799710912, 555272293, 740900592, 436598774,
135907615, 225557554, 858703175, 670091098, 804622912, 560870805, 792263603, 535090320, 465757917, 881015086, 235659378, 419752235, 71274010,
89913920, 739287384, 424871374, 225828220, 396882156, 666263678, 276680656, 588790077, 120659631, 823060123, 588124584, 311334033, 563596054,
345493485, 630837481, 415629308, 770030628, 939990643, 817673868, 540177352, 16967037, 956780858, 849093072, 299797304, 534044364, 645739429,
224846468, 326543561, 585372166, 110806401, 152814937, 911728988, 753576957, 748447575, 425930844, 220852649, 369657670, 615062015, 156993122, 852915259,
631616491, 103572765, 131848643, 724722497, 373065583, 409473030, 741484587, 566017368, 53491733, 41140196, 2656517, 658408166, 236112313, 61455249,
41127189, 947505111, 812148547, 953120555, 822302112, 900904475, 716793763, 416673201, 747256265, 909214033, 731264295, 779829325, 471422680, 258675774,
428044912, 956718512, 823061332, 860053923, 628664827, 784082536, 475656546, 667201159, 240830203, 556234374, 17835060, 573357820, 51022493, 301878823,
507007259, 394325268, 690845212, 456533414, 814208975, 903357464, 706807045, 144285609, 187615923, 379124831, 656249650, 474522471, 846003013, 784813958,
465546961, 569943023, 34769068, 840023761, 573897615, 680964228, 254748812, 997763615, 887321139, 581527603, 53826056, 604201957, 98155191, 813642527,
516020342, 478017339, 843757666, 824532508, 535779470, 955184985, 796079775, 756337790, 397384712, 691336916, 266386365, 256082901, 394885915, 824817042,
531366033, 180339857, 241427881, 541705341, 963179526, 309013596, 496821277, 928882518, 735589017, 917409158, 711676960, 261040262, 397978696, 289886469,
454715587, 138011409, 150014998, 896471044, 665988944, 596984375, 66075539, 816537703, 504247476, 196479568, 263201940, 384557005, 638433085, 521407624,
911216236, 482296066, 832080773, 897106065, 660794255, 533583260, 932848079, 232101082, 328989184, 195253783, 254406179, 255480564, 373977564, 517944652,
898029891, 248907489, 359086142, 249695623, 359799511, 9294822, 878141639, 135011780, 128725991, 464012661, 785885014, 210020257, 277064383, 787722317,
431639687, 270697708, 396768779, 261165022, 376888920, 988885432, 831522554, 290130881, 433213686, 125643201, 103446057, 664258445, 179891871, 192866238,
236330497, 729896901, 309622647, 584430777, 17929126, 787796278, 423906849, 138956364, 125481841, 831226731, 509285571, 514936914, 875977235, 25020668,
895424427, 925689239, 696049716, 648271640, 140511261, 775067166, 393407736, 987897571, 818382747, 775532747, 392976176, 806105884, 453454501, 678300915, 197185686,
389060488, 618055132, 668368607, 176030924, 686532430, 211727497, 921520793, 681082614, 972329090, 782087161, 270125719, 377078039, 826579149, 489392263, 345161688,
525974575, 360261196, 555600772, 300483176, 435481965, 63911994, 961786991, 392699994, 618820615, 125345890, 83580384, 414394902, 661156829, 997100333, 826056647, 681550244,
194456072, 173669802, 178205536, 97724662, 25836433, 374919204, 579757628, 404035359, 637533081, 362611303, 554239242, 430810377, 690202891, 971291489, 770741935, 872507055,
572761318, 177566159, 182479306, 714627158, 256212690, 917289917, 661161319, 448587364, 723391147, 478969819, 783802898, 286832321, 399186755, 275494299, 376181674, 842362391,
509601022, 823494837, 471561391, 341556182, 507391969, 451946822, 727893632, 597599277, 18931518, 228033752, 279546156, 828375200, 479987522, 814675589, 452359671, 36839382,
896471634, 712748781, 248087871, 604990041, 32381032, 969188047, 760600971, 75629931, 973322064, 830808922, 483530825, 500527997, 822833355, 619877387, 61410179, 342328875,
506204989, 969513326, 760479585, 961537312, 744447230, 928412144, 678130637, 451340496, 723935259, 446754559, 714725562, 547496369, 916185723, 554962514, 931109016, 949130294, 719450132,
839677961, 500565687, 903169298, 627583338, 661728417, 144751407, 273749973, 368859309, 358544299, 538527794, 759580740, 340695650, 320701176, 463046756, 923878545, 669527058, 836634161, 495179303,
412472558, 647012657, 641091741, 104423207, 811660936, 445749524, 406303889, 635239198, 263834044, 350519201, 32919054, 888924951, 93543115, 10424917, 669941445, 163489647, 766336473, 356564104,
461338296, 746868580, 716801414, 258112152, 122729016, 70301324, 392228647, 609651263, 406090724, 637742908, 199014634, 223975131, 114549028, 55445332, 919289171, 665344132, 891332311, 609866139, 669990565, 167635678, 560857714, 949840416, 599098623, 26810160, 35035289, 899189037, 724102092, 277845856, 662273163, 154729019, 641858302, 114458210, 151274350, 133867216, 25263362, 882440238, 265641676, 363810036, 726902345, 286962828, 260884776, 355577540, 949391715, 733259734, 253060278, 341283768, 580473385, 996815559, 791956837, 420506807, 474595992, 786528347, 694950651, 227999851, 406007719, 650895255, 715770905, 271222047, 978366259, 797232446, 228105041, 297549070, 285235404, 412668309, 961101801, 765279167, 391568384, 627110067, 708177933, 261246639, 295820577, 437469267, 254884686, 356554768, 993482791, 834728302, 464212467, 777185138, 496181922, 842141769, 456211452, 763238892, 75019064, 1912619, 743430859, 339815243, 697231909, 248517020, 677539934, 210253481, 369305099, 594925061, 418988396, 695453828, 419955222, 698570681, 725593161, 311050879, 156992570, 175075255, 822253485, 506843951, 326466349, 516537979, 248026119, 360947330, 632626395, 131459302, 266331667, 400202994, 416929675, 702753963, 817214529, 504700527, 378412589, 628495525, 795473804, 464038925, 228733013, 332000531, 427096042, 730192072, 887355180, 652198224, 973439826, 825877897, 37587438, 955706112, 564925662, 11938217, 294472516, 472610395, 569149591, 23565891, 37772894, 962436852, 154997830, 198534144, 88288417, 66785929, 840666037, 573235055, 642292274, 178204802, 45255348, 985871715, 153774112, 204673563, 980943319, 860799971, 246556179, 393837471, 868965091, 640490931, 829292241, 563004842, 211328491, 328961026, 641199597, 190611072, 360743071, 631630130, 60692547, 33485545, 194621776, 303324924, 393783234, 703653317, 6884760, 931886507, 607615735, 135403326, 977590824, 877433237, 361729350, 647814977, 3288912, 933063835, 827222613, 583086094, 153390872, 237602732, 899896601, 732819636, 110098726, 155454784, 925732432, 788978616, 926985829, 793767471, 111001885, 164107383, 832693910, 609825049, 400563013, 747922813, 140182214, 229546792, 880363353, 712320764, 688767019, 331566019, 930494710, 817485644, 227578469, 414143830, 31999331, 25502731, 84293614, 132635088, 792475749, 551569854, 483316817, 935849310, 643788303, 259416496, 370193479, 714878082, 522818089, 22805626, 318467228, 616809444, 10339218, 3286257, 154194802, 293757656, 215855297, 419866373, 582095128, 155161349, 871219094, 736252294, 791890834, 580466577, 706558658, 412700916, 116480200, 235470684, 261183420, 527831885, 41871060, 92190108, 356635404, 724730019, 365344518, 745187848, 885372192, 788311266, 180253026, 381169592, 142846757, 309482377, 675641862, 378226673, 831049163, 692224236, 719015851, 471369539, 346674220, 729927275, 803564423, 646977827, 255488683, 554125767, 635061027, 316599219, 955045525, 959926442, 167877571, 388978322, 101467128, 259574869, 152619503, 365326802, 727296186, 518157192, 676000435, 419072667, 870642555, 811893928, 261312913, 596801814, 705289139, 488351662, 470764427, 22929979, 968738798, 22536891, 96706564, 282161148, 381298511, 855064385, 973813043, 43843508, 704309495, 508617320, 722376989, 548564135, 409606695, 926866405, 110603754, 332734496, 175138101, 465708383, 760552909, 640474503, 993607060, 110550725, 966978838, 61293722, 258253457, 647874027, 543064760, 221559389, 687426018, 514376476, 928365761, 382432, 642967064, 433743526, 252284607, 656569202, 36467127, 229157025, 539438485, 239354815, 129075108, 422915545, 384465500, 938016300, 65055436, 303548735, 900894097, 979611303, 753166438, 688574026, 177996750, 542685584, 711073553, 613323094, 583321313, 362335607, 701627125, 603497404, 697344854, 599516313, 598335480, 406114392, 497838832, 209771397, 665537377, 549852360, 11725130, 246945416, 944387672, 117021797, 536352589, 305736815, 403241374, 44333526, 200376637, 643457262, 92629672, 432850695, 254614532, 761742036, 980616345, 218701625, 238769498, 739998376, 115395479, 498275321, 487466538, 247477065, 917383813, 112405989, 618710921, 520189439, 186656170, 661244115, 922274367, 137679708, 428196441, 154758216, 52164646, 407964224, 992328714, 293597273, 311079289, 936438798, 303866133, 927388379, 619660082, 564387793, 394520295, 119555470, 961173714, 258345378, 693467252, 728451462, 483336875, 313745731, 842200852, 37064821, 918722956, 195736390, 452352043, 268658248, 545327486, 460309225, 159051538, 693493939, 108803713, 598771502, 718410042, 823794074, 573240711, 539302139, 829552738, 57809817, 863004505, 130633984, 320831839, 52246392, 254204982, 924987616, 6969216, 436548311, 751529394, 931738281, 223768209, 882323031, 528131615, 497194539, 318687265, 84488230, 730429172, 914192221, 698272323, 856136584, 543154885, 552197751, 354526465, 181275034, 825358466, 129311330, 238869206, 962743401, 63028270, 617510480, 724490559, 946922474, 968885826, 442238994, 290925362, 92882734, 3267552, 524170548, 554339145, 632956018, 636103826, 803166633, 710415362, 958510018, 404096109, 352630983, 546725688, 644688868, 31802547, 621680674, 645193462, 855340030, 613475119, 798820427, 687408970, 953644860, 161802587, 909428578, 962697408, 518254527, 262150583, 124237147, 548754041, 704560366, 765104740, 144418198, 500520027, 622445456, 108112770, 844867960, 595145086, 826210028, 270874667, 184987163, 640459728, 931515886, 235958082, 129911921, 381245290, 427926488, 649497922, 971912825, 960445330, 601329727, 97093644, 882189580, 100699272, 897005263, 730180067, 163612580, 197287973, 105515552, 393351737, 505371743, 181470348, 89379236, 961680558, 657611626, 330383611, 402871520, 656250019, 62500012, 309305169, 376548002, 848210533, 462338504, 405481475, 584902372, 91496018, 964995736, 907746304, 605602957, 368604802, 535469113, 804455783, 415362809, 732306554, 279298778, 581563329, 986089546, 365802617, 562888215, 726200622, 292047291, 811919278, 471890754, 148741317, 153984166, 466940478, 798875089, 202017178, 277564462, 669193957, 220497456, 583473907, 57680367, 28223198, 955845640, 148145498, 204400674, 165560200, 247984381, 280452564, 486567372, 477959824, 890424213, 693581934, 330554903, 450127264, 852576301, 314071888, 589440632, 194713781, 359743951, 563936528, 107253519, 106175737, 200840671, 577280544, 152203749, 341294731, 689430443, 211396571, 438877376, 503774036, 32920590, 702240693, 439187331, 650011165, 344106936, 807993838, 669496275, 507787017, 78552056, 251339790, 575172560, 403611850, 889277257, 92986461, 277632780, 499351866, 100015706, 740178398, 591366813, 241344343, 603442771, 206401348, 543346958, 912995324, 966371294, 532809267, 215881883, 983213208, 126618871, 94824306, 359816702, 763127928, 706446166, 722370370, 634999981, 959468510, 119311987, 951746855, 114031310, 529721902, 280191042, 494712761, 220429487, 92882594, 427073081, 45067016, 341793138, 349532033, 961121775, 523198449, 318900691, 507090719, 297178908, 904915349, 103369522, 959454776, 223037519, 832194124, 979153245, 334394660, 994239325, 393337447, 122857969, 836722382, 20409083, 7123294, 372040444, 793289637, 955251016, 79785394, 539168898, 908102543, 206778109, 249315564, 900227756, 342574516, 97818006, 815271344, 54332868, 867392267, 169744885, 534701924, 515583433, 182430181, 822308335, 956722009, 382209610, 902288302, 284709179, 855767554, 203084114, 743183803, 989382596, 295385048, 105300707, 490317040, 506730054, 658433937, 854579051, 636888608, 823153534, 755251322, 71594132, 116347348, 805551509, 173403652, 931479660, 852518559, 301575333, 453854767, 516164057, 381181787, 382784924, 585870173, 804179147, 66181882, 776870745, 299041904, 254709775, 526749749, 722295376, 755158404, 191333606, 124539732, 942368317, 582807077, 871226253, 86526324, 891039317, 211426931, 153266495, 634365585, 11621273, 281528218, 318475627, 427890624, 623781222, 806783634, 394199818, 337499083, 468315204, 552529863, 911113241, 703140144, 225122367, 925068349, 681819540, 456439285, 757454472, 521141086, 899803515, 140666879, 151853028, 783498570, 450566914, 858157066, 612987099, 143043043, 195915033, 650906049, 224849889, 117541360, 171382345, 975867156, 901348831, 662870901, 288724394, 725332681, 427069297, 886102475, 762083596, 47561937, 98530704, 9723508, 36435587, 203414334, 437452642, 68146458, 180606053, 102225641, 262507440, 596915628, 265684384, 443974280, 973652726, 279783510, 659176369, 233308110, 580185002, 376671281, 880925125, 290041503, 721733796, 804387074, 764547702, 312287599, 794526172, 173151082, 530485291, 465712904, 129895919, 160941178, 534694401, 488882505, 204974009, 224861072, 691383243, 722931703, 702031821, 621239706, 513210478, 328067679, 941484508, 693581360, 687185464, 903903879, 122559718, 34948480, 399433877, 816360867, 977099405, 399856284, 158986916, 837270627, 48768286, 512801159, 414838160, 876725127, 157751102, 832762584, 84947337, 235447438, 905494786, 579872341, 609578816, 762141706, 989408379, 943116653, 366705799, 750100882, 996078595, 96729351, 704796767, 861918038, 250692348, 145537208, 833506015, 471751253, 501566601, 671851273, 917456432, 475203899, 539908861, 77335451, 759976633, 32161976, 685491926, 662470801, 962029492, 428489549, 510044689, 16314376, 701729927, 509461852, 704118423, 732767375, 166881085, 935848692, 589253512, 959953716, 653731621, 701370756, 152892128, 969845836, 706227179, 215253284, 213485535, 366489078, 532459236, 550011683, 916065317, 228755050, 290171778, 344517581, 538375521, 950874879, 767827843, 35087390, 953049762, 939924094, 779579287, 20197220, 957041030, 169974854, 273571212, 481413567, 913483101, 680524280, 328798623, 980547554, 945999012, 584516504, 171150589, 232581597, 484554393, 474590493, 985905828, 582735373, 219589354, 454536568, 980645752, 885326361, 859739658, 986161213, 78984106, 512429672, 149156304, 567651453, 277295759, 331026449, 821802369, 10433692, 198434282, 2179388, 199804015, 341062832, 895510256, 952498866, 136382773, 886163227, 21773166, 246563111, 760695925, 424031510, 133817097, 300493379, 904986725, 56315199, 434937848, 497686916, 336050456, 185249052, 729605712, 171008026, 719616531, 561201811, 518558957, 133065586, 680903467, 731922562, 897296553, 389725749, 231644354, 640260965, 751518597, 721839770, 933542500, 667687453, 844166739, 794690208, 117163793, 122031916, 790901550, 187416359, 940787637, 548356771, 681848627, 406104474, 416587276, 208309720, 40304179, 194526448, 32107312, 68859825, 800207114, 556484344, 794952648, 467397073, 636338169, 440307713, 601783170, 684786652, 110428518, 391099313, 542805178, 704044950, 188511728, 576037261, 952375690, 362509831, 545264311, 168942811, 178137998, 730582736, 321489912, 330869674, 542200308, 13991613, 928645246, 778660724, 478249145, 36023057, 13304245, 221344012, 404341416, 189475175, 361063935, 771499923, 545638647, 764916186, 553061524, 697753284, 439391297, 320538934, 705683505, 18099315, 121590590, 660666159, 427576114, 946989771, 21140792, 466208504, 80561442, 453421084, 76035593, 537964846, 266238020, 387783283, 987055814, 473700720, 180137702, 830479229, 915007947, 413032731, 101494482, 134560369, 565995698, 374457668, 67302722, 914014791, 167995992, 735160941, 831934026, 212392803, 808110278, 694749025, 794602128, 493281615, 413513711, 837333252, 123530469, 227130882, 925106420, 519486064, 531864738, 695878632, 906765217, 516533840, 570258456, 414031247, 387503671, 939443634, 460646515, 325311629, 254768363, 520020830, 666640488, 31891115, 712902758, 105045771, 881801831, 752985175, 200338552, 394974987, 507044374, 660304041, 60497028, 151503259, 65758484, 719990625, 225664780, 382749060, 574181884, 156221331, 144195407, 213518621, 281927820, 192189387, 262476135,
768247614, 437868413, 810767907, 546253976, 798388708, 544909799, 901962470, 775540886, 212828852, 420826660, 779841044, 578473578, 632472082, 307427831, 113361597, 292968779, 58128280, 206333888, 797579671, 709138336, 155886344, 449723390, 427221677, 16435876, 339221871, 864548322, 905399350, 21085639, 451390324, 137320387, 49494083, 357851223, 955422250, 194101470, 517432783, 342587184, 643999076, 620255223, 301720300, 960304041, 604499673, 590540151, 639205845, 684700972, 300880586, 32870135, 308137042, 72274030, 973074166, 427110654, 341183034, 188362278, 831493260, 194088200, 754645700, 65570251, 328017524, 237562869, 844473853, 295796373, 260116589, 152474693, 631777585, 921261612, 355389747, 394023047, 556330669, 821514284, 263370458, 261275635, 295520061, 351329092, 665806748, 117729286, 750867273, 313749837, 765675705, 369338974, 200026002, 264084718, 301558362, 493267549, 80746550, 77835102, 490856205, 924318753, 562116925, 93177789, 880870332, 757095566, 628813053, 279465429, 509851567, 68100434, 567574269, 210177469, 873692245, 849118804, 650907238, 430328023, 429834082, 15034892, 490879892, 164053739, 74663714, 358622761, 471168026, 178706991, 295155594, 853832087, 177046205, 644837700, 884556674, 87157551, 115210415, 575838608, 118650229, 610166529, 189240187, 778869568, 865542848, 159072927, 63254738, 582169798, 135977267, 755363057, 717167922, 945567783, 477464294, 494059270, 869620314, 306345464, 700133516, 995421552, 936570861, 496421526, 754934061, 161348929, 321069418, 321896463, 695848288, 99806917, 16308482, 769156046, 639985648, 45015195, 593980324, 981585587, 409942218, 642166708, 282341338, 415698679, 19405262, 918636761, 44480710, 997674478, 434855697, 807387958, 279113086, 524943039, 622558837, 240951725, 902850065, 830728358, 524927674, 104154837, 351441928, 786531795, 244654275, 602382212, 599548141, 341673038, 518295157, 208747647, 33837064, 269489619, 757781253, 747113813, 552938683, 367242266, 300860628, 892977624, 140290402, 601806599, 72119456, 495512198, 607540226, 596479384, 642277898, 696158641, 42909137, 527703397, 686029380, 844304603, 940692955, 384071027, 660388519, 853980095, 394716654, 353233048, 694422464, 983320199, 915818767, 456867275, 542894261, 741851791, 569410164, 825796260, 227526087, 173020009, 800766104, 350571277, 340505117, 461199987, 833929845, 479279647, 96869033, 36467873, 773234915, 420589203, 841784809, 589158392, 946217273, 829572647, 509231114, 987229687, 448901895, 898280722, 933950773, 900168164, 859045551, 782227731, 615031007, 326149070, 963491846, 55101682, 851626127, 863481804, 113887992, 420197804, 733529029, 691752942, 240177701, 737404270, 180969318, 651422485, 858535631, 39071180, 682895135, 720387478, 597038233, 581352255, 21949390, 463934553, 405014592, 262906421, 716164469, 918129238, 46655075, 612115210, 754134462, 60160511, 533118064, 651296149, 825566869, 269444163, 910346346, 472335610, 25817290, 736692185, 500898865, 720352279, 89073592, 930281067, 676996377, 139788424, 923377433, 666294909, 817003427, 487373940, 533872470, 955021844, 208087928, 337445437, 916602408, 788550031, 116331133, 222166191, 827882950, 679511681, 948084515, 954239932, 763721385, 619922149, 645810277, 418591864, 105141286, 371829372, 626335868, 448877662, 654694069, 540336945, 466911258, 199598050, 887388393, 75462984, 203757226, 743195377, 491346554, 353452879, 918624066, 243170987, 385358384, 211887057, 274348265, 25198680, 372524840, 256968223, 386009376, 319438318, 331809183, 246623683, 376515043, 371705980, 691857737, 38146862, 389329168, 468930254, 407856540, 541910641, 516022738, 794253898, 931258785, 660822162, 666344509, 167175201, 466455112, 803663517, 933500451, 774106901, 232958681, 409461789, 688001007, 356070661, 943159460, 902997698, 920391252, 894157415, 200600773, 491358697, 415184228, 957394038, 982122188, 128224671, 922965166, 46951748, 829698419, 897545874, 465377602, 206118443, 536761092, 386186314, 60723047, 471497908, 529127766, 445781900, 107092421, 639272760, 930798142, 324332811, 711866252, 924204839, 235698962, 9693336, 60792387, 697790644, 115478303, 845160399, 617960346, 888209971, 130077332, 950617111, 190911483, 110546333, 731516056, 230104263, 463386418, 732281747, 569254212, 982542148, 752472145, 387590978, 991737583, 904823081, 398737741, 757612985, 446705889, 892427314, 913964027, 865910166, 644357242, 365751827, 299736400, 715654127, 120856595, 397127338, 754224892, 703185688, 885915185, 5977070, 383752008, 41150664, 821399955, 956035735, 992998040, 338910409, 899453941, 191590154, 79424782, 591389323, 846055269, 164597384, 890852528, 294228729, 754300921, 61252166, 883047437, 358961771, 517058154, 667289805, 4208756, 681987727, 849656217, 413369562, 898265168, 551164705, 176504518, 148311065, 545790286, 927640764, 739009752, 354928460, 181167419, 280183278, 321813369, 602505459, 707031325, 414062547};
void solve(){
int n; cin >> n;
if(n <= 1000000){
if(n <= 3) cout << 1;
else{
int last1 = 1, last2 = 1, res;
for(int i = 4; i <= n; i++){
res = (3 * last1 - 2 * last2 + i * i - 1) % mod;
last2 = last1;
last1 = res;
}
cout << res;
}
}
else{
int pos = (n / 1000000) * 2;
if(n % 1000000 == 0) cout << a[pos - 1];
else if(n % 1000000 == (1000000 - 1)) cout << a[pos - 2];
else{
int last1 = a[pos - 1], last2 = a[pos - 2], res;
for(int i = n / 1000000 * 1000000 + 1; i <= n; i++){
res = (3 * last1 - 2 * last2 + i * i - 1) % mod;
last2 = last1;
last1 = res;
}
cout << res;
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
}
NguyenKhangNinh_99
Created at
3 likes