1152_D. Neko and Aki's Prank
Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a [trie](https://en.wikipedia.org/wiki/Trie) of all correct bracket sequences of length 2n.

The definition of correct bracket sequence is as follows:

  * The empty sequence is a correct bracket sequence, 
  * If s is a correct bracket sequence, then (\,s ) is a correct bracket sequence, 
  * If s and t are a correct bracket sequence, then st is also a correct bracket sequence. 



For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo 10^9 + 7.

Input

The only line contains a single integer n (1 ≤ n ≤ 1000).

Output

Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo 10^9 + 7.

Examples

Input


1


Output


1


Input


2


Output


3


Input


3


Output


9

Note

The pictures below illustrate tries in the first two examples (for clarity, the round brackets are replaced with angle brackets). The maximum matching is highlighted with blue.

<image> <image>
```python
l=[1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, 1174281, 4260282, 15548694, 57048048, 210295326, 778483932, 892818230, 786724318, 347919346, 355845955, 274146173, 336110626, 508416482, 521006399, 214448866, 997593411, 238896999, 849258736, 819525514, 53182350, 202970081, 945166442, 598349475, 683882441, 92894058, 452668785, 75136294, 196675923, 119906583, 942355177, 971081806, 117114980, 360237618, 942712231, 137580544, 313883953, 475793244, 854651725, 734277125, 39095249, 461071198, 801159097, 64968190, 936719156, 886161553, 639551605, 781314451, 681340193, 107129321, 680026807, 103559391, 682186676, 827551267, 510628237, 427135789, 600593159, 542474853, 821284002, 34030966, 212108296, 552111064, 883592263, 580458832, 835540036, 126388564, 22628138, 362655432, 628650076, 577876876, 73283345, 404323915, 228609761, 734246007, 503315696, 474786457, 786621025, 519844441, 126622248, 232121937, 461707459, 964781967, 444174545, 772222316, 418006179, 579943979, 48479441, 255004523, 149519163, 323014184, 89331782, 201498807, 879409500, 313819128, 148656825, 429282108, 581422264, 553214377, 428884534, 304578144, 685949384, 644505805, 93833863, 403784647, 832234244, 508584425, 948278881, 809571136, 445611926, 332423140, 173000195, 714064794, 116628822, 278519688, 676662450, 515315037, 125220758, 184190736, 383890856, 480000081, 126650091, 86979910, 808451709, 451630930, 921270058, 473876008, 646769937, 227033671, 276168190, 12697185, 757160642, 202483804, 116943455, 244139682, 934215874, 158452923, 97994528, 209136188, 812513077, 118261019, 434088376, 117384160, 727697141, 837642470, 132655896, 798015392, 775952773, 792922839, 764879931, 726311620, 830066915, 359922043, 952091491, 152210295, 182338426, 39938439, 35128174, 902646636, 209047086, 22725556, 251866406, 43672812, 503078357, 991343096, 653063739, 48339910, 79488094, 410126004, 546619281, 536643008, 15729744, 32641153, 773429140, 351222791, 178118753, 290822158, 209487213, 421501965, 393411119, 48310849, 206064336, 933840113, 383521934, 260247320, 300575894, 258016806, 861961462, 503317518, 289465950, 205742458, 965192988, 860838962, 612930989, 988868236, 692804611, 949808891, 158619989, 178478976, 656318591, 935888274, 594861602, 212504527, 197101944, 488966659, 561894038, 429319218, 452488972, 166318639, 625132009, 902887424, 864420332, 916156275, 98705298, 854694297, 349260433, 494421728, 633282503, 279864836, 243596071, 739349517, 770783447, 238812351, 18320172, 943321855, 747027778, 587801022, 352326238, 384356475, 659969891, 248924879, 943334805, 73371413, 178956400, 233438997, 94556124, 804781642, 113398542, 551897469, 72519241, 82549791, 509896387, 83827011, 356028512, 303296016, 390306785, 657022030, 464371224, 944104658, 343575359, 762229649, 822363169, 245293123, 766640045, 294291853, 133952039, 220290975, 943649890, 321501293, 833289741, 784922366, 405744219, 530715909, 620437844, 11611272, 828525996, 937378965, 458914582, 414889108, 186018763, 749887062, 87989481, 55886074, 736617689, 341197582, 17228846, 617689322, 804101956, 903076775, 98319282, 528089640, 461743124, 782942141, 82422628, 319537334, 88043058, 306801051, 542873338, 87819422, 465447307, 799568629, 975457975, 981268163, 513413366, 277319289, 45482685, 608310648, 333645167, 42492538, 90835075, 316094777, 746062140, 949995418, 171734290, 391028054, 835144212, 738966944, 547487595, 185412017, 176355329, 219911742, 70400092, 387509540, 906481553, 987149700, 500784758, 125325184, 869740064, 999893398, 164984755, 930117545, 657010659, 123257692, 424856034, 552743218, 184931575, 731307947, 64903761, 431470115, 333568319, 713240357, 662663489, 97641445, 370615844, 848298226, 278661556, 826018292, 31838269, 401165432, 281668873, 886207297, 122232045, 417432333, 486737668, 375497685, 766171974, 542002482, 863934476, 77832072, 837135351, 182727912, 883577248, 721401797, 871352722, 96373726, 522425701, 536349386, 630762417, 787392490, 23805397, 507956382, 461503163, 71726115, 618689038, 943008913, 113268710, 312778511, 836482002, 624222414, 878017876, 986936158, 63031877, 316979977, 131631035, 63038786, 355616568, 724661479, 333664142, 181914780, 436447148, 898609769, 663457398, 659379714, 392454251, 12669528, 903992102, 476374148, 316368147, 90392579, 557340517, 448808914, 182133812, 225359668, 808448727, 688086493, 442960289, 683937353, 485963477, 308485073, 890681010, 72684064, 57234135, 774455177, 267805522, 771768761, 6098266, 220366179, 366000794, 793333460, 864455402, 956074672, 664016903, 630673596, 979578951, 419921513, 881083493, 597187057, 856446379, 54047225, 693970948, 873422393, 282886954, 644264998, 860347601, 119895585, 283479471, 519986253, 816523644, 66832216, 543768713, 614816297, 166601192, 320952360, 379348377, 26136448, 197730425, 655766372, 460581382, 207978233, 99021052, 269775043, 74158462, 418326072, 988044944, 307537543, 240660439, 265956167, 465824590, 976630677, 548433887, 549409535, 269926647, 646212242, 471795581, 896022900, 33108198, 309018900, 573413525, 548833238, 728732265, 951572105, 62448659, 703336805, 113031230, 607758383, 137765647, 881099721, 391255515, 901883059, 531248881, 821743512, 596607866, 422243650, 933777784, 242341144, 805390173, 350461238, 830213159, 245094858, 857768048, 218783758, 858028212, 495606600, 608849415, 714459946, 687960612, 948463089, 32682, 795552363, 673396205, 228454570, 133703002, 3112053, 844662262, 721758359, 182280845, 950342575, 796155000, 63689540, 309812047, 438719405, 366111352, 95696826, 296478421, 904956013, 369725313, 357451142, 47733681, 308344913, 320281313, 599344160, 13921921, 663831108, 132574468, 885056263, 840671481, 676169302, 139295812, 258208619, 592157991, 761901575, 142454833, 299702654, 495761523, 888809591, 104549631, 175465462, 292920150, 584499101, 573679842, 128635314, 236383179, 862035230, 110986048, 731804942, 993647432, 746189529, 467216224, 554057120, 517244686, 157592431, 655562353, 620632991, 316630647, 85089599, 3726444, 576285033, 928970336, 380253777, 359525609, 576932584, 341967422, 533436792, 935722398, 122828500, 362006261, 248987300, 817257641, 906273861, 829394369, 526605667, 582661484, 370655577, 882805119, 753297511, 81791288, 316611255, 185264993, 666225844, 813053846, 315572368, 7438708, 101639442, 847352407, 7361464, 455867504, 1163613, 277884625, 695446595, 702659456, 229118130, 888237935, 695612236, 795282452, 158199573, 846044262, 987819716, 345349078, 841539968, 901727083, 709050100, 503739619, 14825889, 878511475, 796673314, 406538115, 902388885, 927775097, 867418048, 50029940, 846478507, 29788443, 361089455, 243429091, 564385190, 101176236, 471093640, 78389731, 61344214, 896237857, 943210382, 748603085, 487617534, 960782037, 280990439, 338839050, 364966819, 897591613, 239205605, 231883826, 888568706, 352895224, 234659531, 202465711, 747150346, 944580974, 623637770, 977244794, 409076311, 644222090, 921930604, 879387216, 132503849, 88740389, 910328654, 202013463, 114078731, 262855538, 504650505, 853619015, 557249827, 859593512, 782879502, 161588334, 290651237, 976886584, 539505231, 778151014, 425402192, 569549764, 171990975, 480916433, 550645889, 71155583, 156065139, 499692059, 80534761, 418595649, 488668178, 483262353, 761079127, 870633587, 582698686, 397416556, 822038326, 114261506, 24622713, 443392919, 951731173, 817492184, 18330423, 870833154, 834533088, 117896956, 94498840, 536131881, 64007453, 449923986, 821574370, 757613711, 74723964, 425578023, 919147061, 692033356, 467140194, 373099004, 252086810, 47599235, 287686980, 488329506, 304736267, 299921437, 487263176, 570386721, 155626518, 135120313, 780256499, 943269485, 439311458, 670666024, 820144824, 655910522, 349408761, 973209540, 677034872, 799353311, 291824074, 435161693, 231559494, 329403708, 2378980, 212710521, 920578026, 48047965, 550520588, 30545354, 69630519, 773962707, 829864195, 905590682, 611119572, 260204078, 634457375, 968471787, 369265835, 425686971, 38771751, 183683590, 747131861, 960719728, 915994433, 866159020, 473015288, 53506151, 124948573, 343917587, 589872578, 742294532, 14495852, 377992279, 338934871, 28241227, 447328270, 892278625, 134942590, 464657765, 668660637, 250672558, 737001081, 455948587, 309079478, 40504754, 181925242, 361072832, 758358698, 665940970, 43517628, 382558658, 948135945, 911525107, 499528803, 734538281, 204256642, 716926919, 415293736, 592211534, 424766655, 211715017, 811989654, 973185261, 71283395, 669909261, 482493386, 155893078, 159427226, 93862352, 216394917, 81081646, 180373727, 943312894, 438886068, 519120891, 113649471, 447020879, 739772797, 242921087, 74228901, 220425653, 391801216, 971741486, 261900778, 41122455, 852161905, 415634960, 431598449, 106918318, 819689988, 83691209, 268351949, 75997009, 544684771, 842793534, 394127480, 536977905, 273669961, 13154017, 674697744, 120570063, 173038062, 155289228, 729866854, 305834431, 254366798, 948146714, 392601387, 39480327, 1894544, 754109866, 572739979, 929037081, 90035951, 874246352, 59675925, 1639774, 365008783, 737618194, 547055796, 90532616, 469020494, 633699042, 164043064, 186471361, 193622327, 424472933, 626586210, 89128552, 996907354, 177728313, 771495880, 74281199, 969142217, 325059319, 798380593, 121126553, 471553701, 763095828, 455627020, 105743124, 341748301, 709962931, 111837265, 318531149, 930733897, 988695586, 830870739, 30656108, 122689687, 217360479, 391706796, 741471890, 523325838, 141398412, 107925116, 851092099, 271148809, 117970195, 863018934, 735447523, 857990960, 509742870, 500498218, 573794852, 447759458, 684941990, 844729133, 629225108, 222106593, 392879106, 533068281, 850626054, 45899995, 593638907, 934676342, 132318000, 499023155, 436171271, 552883679, 792295609, 645824803, 886827414, 706444268, 616896524, 78301802, 260254975, 901788810, 642418894, 305553206, 618273364, 788645719, 325110782, 587778720, 111711831, 542577686, 12630481, 256730080, 990724443, 869772036, 424356626, 206165254, 769304584, 613851764, 109177953, 544965142, 144527275, 685309657, 63128159, 657300159, 183652896, 321430751, 502528496, 818667858, 499495550, 376529503, 107701542, 391726460, 621975044, 124468824, 238513581, 896376532, 184309119, 932750151, 687110877, 429731291, 281410514, 593103008, 412518197, 620794804, 197857848, 88614112, 15607459, 45223178, 833816631, 377769395, 213918106, 940598221, 989987019, 484564200, 910451483, 875358514, 505257001, 732867688, 292446139, 82609509, 52728457, 38430250, 314974394, 335096325, 728604989, 447007395, 890184550, 517695501, 24770755, 921881760, 351326827, 217344338, 960947743, 75924321, 424019996, 694255122, 188892581, 834256730, 557264777, 697776343, 266829437, 874344960, 637341357, 423320860, 482111820, 814393690, 840475831, 679228153, 655235288, 877941507, 207328718, 248957988, 285894421, 395481136, 249742236, 430609643, 401495572, 954688273, 245064797, 922491926, 270272637, 115775092, 143669332, 849150685, 583597813, 588026197, 272442482, 187450294, 678335714, 259782599, 242688362, 534917942, 253525093, 210730219, 722032462, 965259266, 617034309, 393073110, 313721419, 56306249, 343735952, 636787318, 261702273, 321718608, 531249357, 37579442, 73077892, 579187843, 325446335, 501118772, 558299622, 192686246, 661106091, 878219067, 47659047, 403148139, 250519042, 920205385, 215748488, 432798303, 106669575, 886085854, 25864307, 514447542, 29281400, 401866153, 903783456, 915095654, 535826789, 833110881, 756854001, 137783625, 180168764, 811262396, 311635063, 273281805, 633829322, 440767894, 345547294, 949734795, 792150353, 189238431, 71998606, 947591062, 679349515, 606781339, 966875176, 224259878, 692359925, 820312559, 804141891, 368969629, 142139205, 939356275, 969189655, 414138837, 15044142, 176100512, 562397884, 787042742, 956416385, 176740934, 146380347, 557357153, 425360915, 337919072, 428764947, 894643220, 160943702, 738297521, 759110632, 102698674, 268473967, 60052640, 621526957, 895441155, 644577760, 559548335, 226477730, 804947440, 854802118, 212773938, 369618916, 630074277, 683336252, 733742391, 689759642, 536324741, 12232850, 588395062, 311834902, 822700906, 918264540, 383029467, 838692046, 779820735, 231894781, 127968797, 146143427, 514318905, 780214430, 532924900, 362245605, 616904934, 159952118, 974181243, 464233843, 638310707, 136785681, 650317857, 735148405, 813970111, 346354503, 450347746, 226170708, 949341109, 686265960, 457248555, 802620126, 406473234, 620525961, 499658652, 996948192, 432517005, 531544188, 736310230, 364121646, 51128023, 702339436, 491727676, 778790268, 991720904, 233882858, 447952019, 967158671, 131392770, 249020049, 17082876, 698852882, 940026909, 688883348, 292899252, 464708546, 689894359, 844446056, 660596379, 835026416, 434755394, 40833306, 988981175, 833869084, 148016296, 289878633, 691707616, 661734006, 227811471, 658581356, 651921475, 899658740, 598341579, 491077042, 523084223, 76743680, 345023872, 817961350, 668829460, 244890498, 889263641, 690084579, 789381194, 684971088, 529646577, 281941575, 866121528, 672773016]
n=int(input())
print(sum(l[:n])%1000000007)
```