Problem:


Score : 400 points

Problem Statement

Akari has n kinds of flowers, one of each kind.

She is going to choose one or more of these flowers to make a bouquet.

However, she hates two numbers a and b, so the number of flowers in the bouquet cannot be a or b.

How many different bouquets are there that Akari can make?

Find the count modulo (10^9 + 7).

Here, two bouquets are considered different when there is a flower that is used in one of the bouquets but not in the other bouquet.

Constraints

All values in input are integers.

2 \leq n \leq 10^9

1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)

Input

Input is given from Standard Input in the following format:

n a b

Output

Print the number of bouquets that Akari can make, modulo (10^9 + 7). (If there are no such bouquets, print 0.)

Sample Input 1

4 1 3

Sample Output 1

7

In this case, Akari can choose 2 or 4 flowers to make the bouquet.

There are 6 ways to choose 2 out of the 4 flowers, and 1 way to choose 4, so there are a total of 7 different bouquets that Akari can make.

Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

Print the count modulo (10^9 + 7).



Sample input:
4 1 3


Sample output:
7

Submission status: Wrong Answer

Solution code:
n, a ,b = map(int, input().split())

m = 1000000007

r = [1000000000, 999000000, 998000000, 997000000, 996000000, 995000000, 994000000, 993000000, 992000000, 991000000, 990000000, 989000000, 988000000, 987000000, 986000000, 985000000, 984000000, 983000000, 982000000, 981000000, 980000000, 979000000, 978000000, 977000000, 976000000, 975000000, 974000000, 973000000, 972000000, 971000000, 970000000, 969000000, 968000000, 967000000, 966000000, 965000000, 964000000, 963000000, 962000000, 961000000, 960000000, 959000000, 958000000, 957000000, 956000000, 955000000, 954000000, 953000000, 952000000, 951000000, 950000000, 949000000, 948000000, 947000000, 946000000, 945000000, 944000000, 943000000, 942000000, 941000000, 940000000, 939000000, 938000000, 937000000, 936000000, 935000000, 934000000, 933000000, 932000000, 931000000, 930000000, 929000000, 928000000, 927000000, 926000000, 925000000, 924000000, 923000000, 922000000, 921000000, 920000000, 919000000, 918000000, 917000000, 916000000, 915000000, 914000000, 913000000, 912000000, 911000000, 910000000, 909000000, 908000000, 907000000, 906000000, 905000000, 904000000, 903000000, 902000000, 901000000, 900000000, 899000000, 898000000, 897000000, 896000000, 895000000, 894000000, 893000000, 892000000, 891000000, 890000000, 889000000, 888000000, 887000000, 886000000, 885000000, 884000000, 883000000, 882000000, 881000000, 880000000, 879000000, 878000000, 877000000, 876000000, 875000000, 874000000, 873000000, 872000000, 871000000, 870000000, 869000000, 868000000, 867000000, 866000000, 865000000, 864000000, 863000000, 862000000, 861000000, 860000000, 859000000, 858000000, 857000000, 856000000, 855000000, 854000000, 853000000, 852000000, 851000000, 850000000, 849000000, 848000000, 847000000, 846000000, 845000000, 844000000, 843000000, 842000000, 841000000, 840000000, 839000000, 838000000, 837000000, 836000000, 835000000, 834000000, 833000000, 832000000, 831000000, 830000000, 829000000, 828000000, 827000000, 826000000, 825000000, 824000000, 823000000, 822000000, 821000000, 820000000, 819000000, 818000000, 817000000, 816000000, 815000000, 814000000, 813000000, 812000000, 811000000, 810000000, 809000000, 808000000, 807000000, 806000000, 805000000, 804000000, 803000000, 802000000, 801000000, 800000000, 799000000, 798000000, 797000000, 796000000, 795000000, 794000000, 793000000, 792000000, 791000000, 790000000, 789000000, 788000000, 787000000, 786000000, 785000000, 784000000, 783000000, 782000000, 781000000, 780000000, 779000000, 778000000, 777000000, 776000000, 775000000, 774000000, 773000000, 772000000, 771000000, 770000000, 769000000, 768000000, 767000000, 766000000, 765000000, 764000000, 763000000, 762000000, 761000000, 760000000, 759000000, 758000000, 757000000, 756000000, 755000000, 754000000, 753000000, 752000000, 751000000, 750000000, 749000000, 748000000, 747000000, 746000000, 745000000, 744000000, 743000000, 742000000, 741000000, 740000000, 739000000, 738000000, 737000000, 736000000, 735000000, 734000000, 733000000, 732000000, 731000000, 730000000, 729000000, 728000000, 727000000, 726000000, 725000000, 724000000, 723000000, 722000000, 721000000, 720000000, 719000000, 718000000, 717000000, 716000000, 715000000, 714000000, 713000000, 712000000, 711000000, 710000000, 709000000, 708000000, 707000000, 706000000, 705000000, 704000000, 703000000, 702000000, 701000000, 700000000, 699000000, 698000000, 697000000, 696000000, 695000000, 694000000, 693000000, 692000000, 691000000, 690000000, 689000000, 688000000, 687000000, 686000000, 685000000, 684000000, 683000000, 682000000, 681000000, 680000000, 679000000, 678000000, 677000000, 676000000, 675000000, 674000000, 673000000, 672000000, 671000000, 670000000, 669000000, 668000000, 667000000, 666000000, 665000000, 664000000, 663000000, 662000000, 661000000, 660000000, 659000000, 658000000, 657000000, 656000000, 655000000, 654000000, 653000000, 652000000, 651000000, 650000000, 649000000, 648000000, 647000000, 646000000, 645000000, 644000000, 643000000, 642000000, 641000000, 640000000, 639000000, 638000000, 637000000, 636000000, 635000000, 634000000, 633000000, 632000000, 631000000, 630000000, 629000000, 628000000, 627000000, 626000000, 625000000, 624000000, 623000000, 622000000, 621000000, 620000000, 619000000, 618000000, 617000000, 616000000, 615000000, 614000000, 613000000, 612000000, 611000000, 610000000, 609000000, 608000000, 607000000, 606000000, 605000000, 604000000, 603000000, 602000000, 601000000, 600000000, 599000000, 598000000, 597000000, 596000000, 595000000, 594000000, 593000000, 592000000, 591000000, 590000000, 589000000, 588000000, 587000000, 586000000, 585000000, 584000000, 583000000, 582000000, 581000000, 580000000, 579000000, 578000000, 577000000, 576000000, 575000000, 574000000, 573000000, 572000000, 571000000, 570000000, 569000000, 568000000, 567000000, 566000000, 565000000, 564000000, 563000000, 562000000, 561000000, 560000000, 559000000, 558000000, 557000000, 556000000, 555000000, 554000000, 553000000, 552000000, 551000000, 550000000, 549000000, 548000000, 547000000, 546000000, 545000000, 544000000, 543000000, 542000000, 541000000, 540000000, 539000000, 538000000, 537000000, 536000000, 535000000, 534000000, 533000000, 532000000, 531000000, 530000000, 529000000, 528000000, 527000000, 526000000, 525000000, 524000000, 523000000, 522000000, 521000000, 520000000, 519000000, 518000000, 517000000, 516000000, 515000000, 514000000, 513000000, 512000000, 511000000, 510000000, 509000000, 508000000, 507000000, 506000000, 505000000, 504000000, 503000000, 502000000, 501000000, 500000000, 499000000, 498000000, 497000000, 496000000, 495000000, 494000000, 493000000, 492000000, 491000000, 490000000, 489000000, 488000000, 487000000, 486000000, 485000000, 484000000, 483000000, 482000000, 481000000, 480000000, 479000000, 478000000, 477000000, 476000000, 475000000, 474000000, 473000000, 472000000, 471000000, 470000000, 469000000, 468000000, 467000000, 466000000, 465000000, 464000000, 463000000, 462000000, 461000000, 460000000, 459000000, 458000000, 457000000, 456000000, 455000000, 454000000, 453000000, 452000000, 451000000, 450000000, 449000000, 448000000, 447000000, 446000000, 445000000, 444000000, 443000000, 442000000, 441000000, 440000000, 439000000, 438000000, 437000000, 436000000, 435000000, 434000000, 433000000, 432000000, 431000000, 430000000, 429000000, 428000000, 427000000, 426000000, 425000000, 424000000, 423000000, 422000000, 421000000, 420000000, 419000000, 418000000, 417000000, 416000000, 415000000, 414000000, 413000000, 412000000, 411000000, 410000000, 409000000, 408000000, 407000000, 406000000, 405000000, 404000000, 403000000, 402000000, 401000000, 400000000, 399000000, 398000000, 397000000, 396000000, 395000000, 394000000, 393000000, 392000000, 391000000, 390000000, 389000000, 388000000, 387000000, 386000000, 385000000, 384000000, 383000000, 382000000, 381000000, 380000000, 379000000, 378000000, 377000000, 376000000, 375000000, 374000000, 373000000, 372000000, 371000000, 370000000, 369000000, 368000000, 367000000, 366000000, 365000000, 364000000, 363000000, 362000000, 361000000, 360000000, 359000000, 358000000, 357000000, 356000000, 355000000, 354000000, 353000000, 352000000, 351000000, 350000000, 349000000, 348000000, 347000000, 346000000, 345000000, 344000000, 343000000, 342000000, 341000000, 340000000, 339000000, 338000000, 337000000, 336000000, 335000000, 334000000, 333000000, 332000000, 331000000, 330000000, 329000000, 328000000, 327000000, 326000000, 325000000, 324000000, 323000000, 322000000, 321000000, 320000000, 319000000, 318000000, 317000000, 316000000, 315000000, 314000000, 313000000, 312000000, 311000000, 310000000, 309000000, 308000000, 307000000, 306000000, 305000000, 304000000, 303000000, 302000000, 301000000, 300000000, 299000000, 298000000, 297000000, 296000000, 295000000, 294000000, 293000000, 292000000, 291000000, 290000000, 289000000, 288000000, 287000000, 286000000, 285000000, 284000000, 283000000, 282000000, 281000000, 280000000, 279000000, 278000000, 277000000, 276000000, 275000000, 274000000, 273000000, 272000000, 271000000, 270000000, 269000000, 268000000, 267000000, 266000000, 265000000, 264000000, 263000000, 262000000, 261000000, 260000000, 259000000, 258000000, 257000000, 256000000, 255000000, 254000000, 253000000, 252000000, 251000000, 250000000, 249000000, 248000000, 247000000, 246000000, 245000000, 244000000, 243000000, 242000000, 241000000, 240000000, 239000000, 238000000, 237000000, 236000000, 235000000, 234000000, 233000000, 232000000, 231000000, 230000000, 229000000, 228000000, 227000000, 226000000, 225000000, 224000000, 223000000, 222000000, 221000000, 220000000, 219000000, 218000000, 217000000, 216000000, 215000000, 214000000, 213000000, 212000000, 211000000, 210000000, 209000000, 208000000, 207000000, 206000000, 205000000, 204000000, 203000000, 202000000, 201000000, 200000000, 199000000, 198000000, 197000000, 196000000, 195000000, 194000000, 193000000, 192000000, 191000000, 190000000, 189000000, 188000000, 187000000, 186000000, 185000000, 184000000, 183000000, 182000000, 181000000, 180000000, 179000000, 178000000, 177000000, 176000000, 175000000, 174000000, 173000000, 172000000, 171000000, 170000000, 169000000, 168000000, 167000000, 166000000, 165000000, 164000000, 163000000, 162000000, 161000000, 160000000, 159000000, 158000000, 157000000, 156000000, 155000000, 154000000, 153000000, 152000000, 151000000, 150000000, 149000000, 148000000, 147000000, 146000000, 145000000, 144000000, 143000000, 142000000, 141000000, 140000000, 139000000, 138000000, 137000000, 136000000, 135000000, 134000000, 133000000, 132000000, 131000000, 130000000, 129000000, 128000000, 127000000, 126000000, 125000000, 124000000, 123000000, 122000000, 121000000, 120000000, 119000000, 118000000, 117000000, 116000000, 115000000, 114000000, 113000000, 112000000, 111000000, 110000000, 109000000, 108000000, 107000000, 106000000, 105000000, 104000000, 103000000, 102000000, 101000000, 100000000, 99000000, 98000000, 97000000, 96000000, 95000000, 94000000, 93000000, 92000000, 91000000, 90000000, 89000000, 88000000, 87000000, 86000000, 85000000, 84000000, 83000000, 82000000, 81000000, 80000000, 79000000, 78000000, 77000000, 76000000, 75000000, 74000000, 73000000, 72000000, 71000000, 70000000, 69000000, 68000000, 67000000, 66000000, 65000000, 64000000, 63000000, 62000000, 61000000, 60000000, 59000000, 58000000, 57000000, 56000000, 55000000, 54000000, 53000000, 52000000, 51000000, 50000000, 49000000, 48000000, 47000000, 46000000, 45000000, 44000000, 43000000, 42000000, 41000000, 40000000, 39000000, 38000000, 37000000, 36000000, 35000000, 34000000, 33000000, 32000000, 31000000, 30000000, 29000000, 28000000, 27000000, 26000000, 25000000, 24000000, 23000000, 22000000, 21000000, 20000000, 19000000, 18000000, 17000000, 16000000, 15000000, 14000000, 13000000, 12000000, 11000000, 10000000, 9000000, 8000000, 7000000, 6000000, 5000000, 4000000, 3000000, 2000000, 1000000]
v = [698611116, 869544707, 598245292, 822439091, 780882948, 3258987, 205951465, 216046746, 646654592, 241289571, 847549272, 954958912, 73146164, 576368335, 823495900, 847645126, 373451745, 676511002, 859917803, 301196854, 377329025, 131384366, 536841269, 496442755, 741626808, 532702135, 917041303, 680128316, 165393390, 152233223, 492741665, 967284733, 121000338, 303338827, 512634493, 321900901, 899946391, 881482632, 916291845, 992656683, 965785236, 185438078, 31503476, 462880311, 281329488, 346966053, 946149627, 48160594, 708233401, 567473423, 315103615, 706334445, 10430738, 390019735, 105359006, 954913, 176966527, 883278906, 217298111, 682873215, 83868974, 804861409, 923333660, 737331920, 713258160, 49031023, 859637374, 698308420, 49389215, 25977209, 778983779, 753042874, 14162538, 362928234, 236455213, 756154604, 793307102, 602742426, 107141741, 213092254, 193781724, 620531822, 237120480, 962540888, 117483873, 260466949, 965683742, 921648059, 364380585, 865440961, 172114298, 634359666, 494166907, 308474522, 351472920, 953634340, 66547751, 763514207, 718623833, 482254337, 586445753, 647630109, 114495791, 22556579, 491466901, 36292292, 759404319, 728620948, 10475577, 600624983, 245795606, 607715125, 701220427, 358757251, 787113234, 687265514, 816701166, 846650652, 799289297, 677395736, 627655552, 754787150, 161362528, 767372800, 304644842, 393556719, 753513874, 322633051, 918860977, 674115061, 256473217, 59342705, 774625892, 640266394, 563796647, 163928347, 281804989, 871117927, 241427979, 749816133, 116667533, 946464959, 885362182, 538609927, 894247956, 175638827, 842203531, 678171399, 946421040, 727416538, 823845496, 804930491, 551060742, 60517502, 983737173, 60625018, 10065330, 885537778, 406024012, 562608724, 814362881, 277813439, 929893103, 906233141, 639655136, 684748812, 100228913, 135625240, 493689107, 72482816, 672850561, 317076664, 751040886, 494210290, 421943723, 341080135, 76770272, 832671304, 269571439, 190395535, 629786193, 162683802, 841656666, 951524114, 541120825, 331910086, 161960209, 496709826, 696623384, 663560047, 423951674, 842065079, 785804644, 369832433, 264688936, 340030191, 986598821, 907800444, 880691101, 264582598, 203191898, 875641535, 15391652, 15655126, 581418893, 819801784, 172096141, 77123823, 574455974, 403652653, 748510389, 513196123, 919717789, 484492064, 628829100, 715264908, 895205045, 514359662, 808691930, 590098114, 624500515, 713448377, 277714559, 828883117, 892168027, 644050694, 897162044, 398781902, 508831870, 945204804, 671734977, 802100365, 48562889, 633292726, 454039189, 439411911, 478982047, 826300950, 564827277, 726089763, 624148346, 113917835, 857241854, 863066876, 812283640, 676526196, 247844667, 178598958, 810551911, 375472836, 217598709, 27236531, 863002719, 398782410, 701050258, 211487466, 219932130, 289594327, 922377372, 811053196, 375297772, 214569244, 534279149, 962670136, 280700600, 414236650, 488906585, 717946122, 206282795, 208761293, 663307737, 155133422, 404149413, 117842065, 212842957, 469928208, 567033437, 555842733, 689189630, 593090119, 852304035, 985546115, 547838438, 322096036, 918513230, 201339230, 827722926, 758245605, 129621197, 282092463, 435887178, 975266085, 632627667, 978119194, 869630152, 765215899, 338121343, 329837066, 933376898, 64814326, 957939114, 188054995, 49187570, 46765164, 815463367, 561011609, 341779962, 314738056, 701506133, 126925175, 825871994, 261970285, 502371023, 819114541, 946867127, 666493603, 682189174, 586444655, 273712630, 384547635, 606241871, 797736554, 180350107, 175504139, 308186532, 147050765, 702823274, 876379959, 256853930, 263645931, 373745190, 310317874, 986708498, 909433461, 919419361, 407518072, 582627184, 137603545, 888146074, 231988936, 769795511, 882121662, 98349682, 9416035, 334326205, 196345098, 744158074, 94331513, 15570863, 573074791, 92255682, 202649964, 322908524, 909458706, 249153339, 218107212, 388728584, 339383292, 368114731, 361583925, 903466878, 490222511, 167087470, 151834896, 483924582, 816929577, 920251227, 262322489, 124804049, 459116722, 456152084, 267193060, 407934361, 936229527, 359960756, 44135644, 965656187, 286273596, 668422905, 181594759, 326159309, 861754542, 484458461, 201307702, 48527183, 564188856, 939889684, 951279549, 48824684, 538771609, 272814771, 465070856, 303076380, 295726547, 596949867, 510650790, 281230685, 626663115, 701453022, 437605233, 724464507, 330711333, 817928963, 859369491, 25058942, 271198437, 523696723, 472759660, 648711554, 185646898, 131772368, 366033520, 206330671, 446477394, 208184231, 26011548, 435904287, 529840945, 34629406, 764368449, 848924691, 401382061, 752550134, 811944661, 508038818, 48053248, 179111720, 907720182, 606870929, 438952959, 811575797, 849974789, 699767918, 100498586, 798895521, 502297454, 462528877, 453019482, 490676632, 956856710, 637939935, 464118005, 777901604, 912368644, 923043932, 457469634, 915265013, 164246193, 370732451, 775025061, 696628828, 551096742, 519397500, 749296077, 565456578, 688809790, 186576440, 593938674, 693305776, 540818053, 141827977, 160150665, 326686486, 996049638, 919273670, 491415383, 553033642, 385377759, 636578562, 152028387, 256141983, 796616594, 442795120, 56547945, 313132653, 46819124, 681756977, 152267158, 385388084, 473379392, 608823837, 91352335, 718498895, 559214642, 167831173, 864869025, 864326453, 662741752, 31131935, 611751357, 97830135, 749724532, 404206040, 985594252, 68718097, 180898306, 16634739, 803187381, 459878625, 503105966, 733333339, 784139777, 352946234, 561745549, 216665960, 863250534, 26031303, 350095207, 732868367, 552133875, 703397904, 183888367, 296229203, 382617671, 726997875, 5003231, 497196934, 302020341, 747407118, 707469729, 99199382, 702004730, 198768464, 832069712, 50590510, 321685608, 424989675, 628514947, 719566487, 278704903, 909210595, 795190182, 754363835, 818036959, 554917439, 432030917, 252551589, 526131620, 325912072, 666247477, 275105629, 741114145, 934281721, 845583555, 675258797, 843321396, 41815820, 382776490, 654611901, 961812918, 462639908, 379404150, 451373308, 268844715, 711553356, 596737944, 155569943, 989944961, 990826116, 551028176, 780072518, 325362513, 263053337, 990779998, 309134554, 392838702, 149586983, 380480118, 209244402, 997474832, 568392357, 343043237, 247662371, 951540811, 125354499, 775305697, 347046911, 987597705, 581830879, 141866945, 358655417, 1277567, 893732627, 952831975, 925347821, 418537348, 274192146, 636177449, 697611981, 987314628, 996164327, 593524514, 833550543, 947549662, 940524812, 937409008, 940338439, 384843585, 316486674, 398078032, 429277690, 715317963, 79716267, 322487421, 59883031, 105419548, 421623838, 808651347, 435327356, 856859395, 917084264, 699739374, 180002392, 878471898, 218129285, 473718967, 115312728, 346091869, 325334066, 11633075, 940567523, 798830099, 241107368, 974886682, 302177126, 529726489, 701445829, 591915968, 882148737, 160684257, 148528617, 868553027, 985084650, 343807435, 825132993, 179518046, 811056092, 405755338, 943653305, 68322490, 189239124, 6734065, 68409439, 383388563, 830567832, 716986954, 715247054, 403351886, 724205533, 184419613, 386027524, 926036911, 836813268, 888287558, 895609896, 624577416, 954840109, 563781682, 580204973, 86117128, 309058615, 164752359, 464599136, 499377092, 332139472, 559947225, 472012302, 142946099, 335416359, 579995261, 522049725, 291733496, 793270300, 776264326, 587220627, 93940075, 472935553, 258379324, 363172638, 450398100, 30977140, 573592106, 204355779, 306832604, 773206631, 318951960, 577786541, 717975101, 299172297, 685707545, 128487469, 954061253, 504962686, 385330357, 841799766, 563432246, 199866123, 957633609, 673464765, 686692315, 668123525, 560006119, 643638805, 358700839, 461415770, 651081062, 460373282, 276894233, 39052406, 780122909, 500780548, 970937898, 648991369, 173539388, 450718279, 607730875, 990918946, 151319402, 160398980, 965429853, 419363534, 611251733, 54062950, 335353644, 898554793, 996097969, 380858207, 183011467, 618898635, 788132977, 217544623, 316439118, 736265527, 192345193, 839849206, 889410460, 353339603, 811637561, 591048681, 277717575, 135498044, 271788964, 479334442, 839079953, 108312174, 167240465, 339464594, 677948390, 103056890, 730341625, 112390913, 702807165, 79874094, 277118392, 270239666, 564758715, 366384665, 113570024, 710729672, 506496856, 136026497, 495022305, 115435332, 91068149, 95182730, 938269070, 481661251, 61570384, 243624360, 173784895, 268838846, 562519302, 116261993, 75307702, 172115341, 464456846, 806047532, 45060610, 740594930, 475812562, 368925948, 763017204, 834860913, 450387329, 492237273, 114985663, 910291942, 946237212, 238087006, 636817583, 724691727, 914456118, 925152039, 958992544, 848952161, 911398531, 557301633, 511371690, 238971581, 616368450, 933245637, 26853683, 630621321, 437843114, 325636655, 34538816, 542432219, 304173654, 105574531, 574053420, 109838563, 187348575, 748566338, 602139210, 23015220, 996122673, 296269301, 917404120, 350016754, 143066173, 547665832, 307390891, 52167191, 66247239, 83489485, 785113347, 349551356, 97136305, 195290384, 555972231, 66404266, 289752035, 677711203, 678320208, 827544702, 509096183, 212938473, 731551699, 457882808, 576798521, 195888993, 827348878, 664989237, 570033864, 80729842, 659224434, 444090941, 747664143, 323214113, 849009131, 261384175, 695345956, 1559745, 244109365, 513365505, 232253360, 82104855, 856259313, 487998999, 250388809, 970055531, 887420150, 159554990, 172428290, 395891998, 797848181, 60050552, 554749550, 243276029, 335160196, 623534362, 972424306, 751231582, 211768084, 583967898, 935080803, 544064410, 802214249, 168203998, 261799937, 661224977, 220108638, 421835306, 697066277, 400295761, 770511792, 14235602, 432775082, 692636218, 60168088, 281863274, 108819476, 47401357, 39417871, 44930135, 112249297, 567277637, 676405347, 934814019, 876297919, 927880474, 804805577, 168891766, 973478770, 56305184, 884343068, 85990869, 440902696, 736550105, 656116726, 888050723, 235861787, 899297830, 840398449, 439729802, 534491822, 459188207, 145404005, 579691190, 526807168, 199888908, 837229828, 595143852, 480748381, 361786913, 1669644, 585237443, 996952918, 808412394, 788878910, 625544428, 371263376, 340941507, 889750731, 86609485, 606322308, 766196482, 5974669, 59469516, 438371670, 27368307, 778773518, 811667359, 746536789, 762479457, 407719831, 228338256, 722054885, 196447201, 497478507, 67347853, 813805606, 294587621, 530389102, 398699886, 172827403, 323604647, 299085602, 721996174, 156530778, 723816384, 82926604, 798967520, 898187927, 544075857, 463847391, 485348706, 886294336, 842267748, 268124147, 76479948, 850500036, 19426633, 881746146, 638587686, 586350670, 968999, 246899319, 565768255, 245341950, 491101308, 288843364, 626497524, 248744620, 336060741, 598816162, 167332441, 933097914, 95936601, 134623568, 682498929, 980250487, 251368199, 690120224, 316220877, 974067448, 259081142, 5832229, 578095319, 641102369]

def factrial(x):
    s = 2
    a = 1
    for i in range(len(r)):
        if n >= r[i]:
            a = a * v[i] % m
            s = r[i] + 1
            break

    for i in range(s,x + 1):
        a = a * i % m

    return(a)

def power_func(a,n,p):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

X = power_func(2,n,m)
X = X- 1
Y = (factrial(n)* pow(factrial(a),m-2,m)*pow(factrial(n-a),m-2,m)) % m
Z = (factrial(n)* pow(factrial(b),m-2,m)*pow(factrial(n-b),m-2,m)) % m
X = (X-Y + m) % m
X = (X-Z + m) % m
print(int(X))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def modInverse(a, p):
    return pow(a, p-2, p)

def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p

def solve(n: int, a: int, b: int):
    p = 10**9+7
    ans = pow(2, n, p) - modBinomial(n, a, p) - modBinomial(n,b,p)
    if ans < 0:
        ans += p
    if ans <= 1:
        print(0)
    else:
        print(ans-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
m=list(map(int, input().split()))
n=m[0]
a=m[1]
b=m[2]
c=0

while n>10:
    if n>100000000:
        c+=494499948
        n-=100000000
    elif n>10000000:
        c+=255718402
        n-=10000000
    elif n>1000000:
        c+=235042059
        n-=1000000
    elif n>100000:
        c+=607723520
        n-=100000
    elif n>10000:
        c+=905611805
        n-=10000
    elif n>1000:
        c+=688423210
        n-=1000
    elif n>100:
        c+=976371285
        n-=100
    elif n>10:
        c+=1024
        n-=10
c+=2**n
c=c-2**a -2**b
print(c%1000000007)

Submission status: Wrong Answer

Solution code:
n, a, b = map(int, input().split())

p = 10**9 + 7
cmb_a = 1
cmb_b = 1

for i in range(1,a+1):
    cmb_a = (cmb_a * (n-i+1) / i) % p
for i in range(1,b+1):
    cmb_b = (cmb_b * (n-i+1) / i) % p
ans = pow(2, n, p) - cmb_a - cmb_b - 1

if ans < 0:
    print(int(ans)+p)
else:
    print(int(ans))

Submission status: Wrong Answer

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# abc156/abc156_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

MAX = 2 * 10**5 + 10
MOD = 10**9 + 7

fac = [1, 1] + [0] * MAX
finv = [1, 1] + [0] * MAX
inv = [1, 1] + [0] * MAX

for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def getP(n, a, b):
    _n = n
    for i in range(1, a):
        _n = (_n * (n - i)) % MOD
    P_a = n
    for i in range(a, b):
        _n = (_n * (n - i)) % MOD
    P_b = _n
    return (P_a, P_b)


def main():
    n, a, b = i2nn()
    all_C = 2**(n) - 1
    P_a, P_b = getP(n, a, b)
    C_a = (P_a * finv[a]) % MOD
    C_b = (P_b * finv[b]) % MOD
    print((all_C - C_a - C_b) % MOD)
    return

main()

Submission status: Wrong Answer

Solution code:
N, a, b = map(int, input().split())

allComb = 2 ** N - 1

factA = 1
factB = 1
factNA = 1
factNB = 1
for indx in range(0, b):
  factB  = factB  * (indx + 1)
  factNB = factNB * (N - indx)
  if indx <= a:
    factA  = factA  * (indx + 1)
    factNA = factNA * (N - indx)

Ans = allComb - int(factNA / factA) - int(factNB / factB)
#Ans = Ans % ((10**9) + 7)

print(Ans)

Submission status: Wrong Answer

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7


def c(n):
    return (n*(n+1)*(2*n+1)-3*n*(n+1))//12
def d(n):
    return n*(n-1)//2
    
print((c(n)-d(a)-d(b))%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def comb(n, k):
    res = 1
    for i in range(k):
        res = (res * (n - i) / (k - i)) % MOD
    return res % MOD


n, a, b = map(int, input().split())

ncn = (2 ** n - 1) % MOD
nca = comb(n, a)
ncb = comb(n, b)

print(int(ncn - nca - ncb))

Submission status: Wrong Answer

Solution code:
import math
m=list(map(int, input().split()))
n=m[0]
a=m[1]
b=m[2]
c=0

while n>10:
    if n>100000000:
        c+=494499948
        n-=100000000
    elif n>10000000:
        c+=255718402
        n-=10000000
    elif n>1000000:
        c+=235042059
        n-=1000000
    elif n>100000:
        c+=607723520
        n-=100000
    elif n>10000:
        c+=905611805
        n-=10000
    elif n>1000:
        c+=688423210
        n-=1000
    elif n>100:
        c+=976371285
        n-=100
    elif n>10:
        c+=1024
        n-=10
    print(n)
c+=2**n
c=c-2**a -2**b
print(c%1000000007)

Submission status: Wrong Answer

Solution code:
n, a, b = map(int, input().split())

p = 10**9 + 7
cmb_a = 1
cmb_b = 1

for i in range(1,a+1):
    cmb_a = (cmb_a * (n-i+1) / i) % p
for i in range(1,b+1):
    cmb_b = (cmb_b * (n-i+1) / i) % p
ans = pow(2, n, p) - cmb_a - cmb_b - 1

print(int(ans))

Submission status: Wrong Answer

Solution code:
import math


def ncr(n, r):
    r = min(r, n - r)
    if n + r < 4000:
        return math.factorial(n) // math.factorial(n-r) // math.factorial(r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = list(range(n - r + 1, n + 1))
    denominator = list(range(1, r+1))
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    result = 1
    for k in range(r):
        result *= numerator[k]
    return result


n, a, b = map(int, input().split())
MOD = 10**9 + 7
cmb_count = 0
for i in range(n):
    if not(i == a or i == b):
        cmb_count += ncr(n, i)
print(cmb_count % MOD)

Submission status: Wrong Answer

Solution code:

n,a,b = map(int,input().split())

mod = 10**9+7
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

ans = power_func(2,n,mod) - comb(n,a,mod)-comb(n,b,mod)
print(ans)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7

n,a,b=map(int,input().split())
com=[]
ans=pow(2,n,MOD)-1


def cmb(k):
    ret=1
    x,y=1,1
    for i in range(1,k+1):
        x*=(n-i+1)%MOD
        x%=MOD
        y*=i
        y%=MOD
    ret=x*pow(y%MOD,MOD-2,MOD)%MOD

    return ret%MOD



ans-=(cmb(a)+cmb(b))%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,a,b=map(int,input().split())
mod=100000007
factorial = [1]

def power_func(a,n,p):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res
for i in range(1, n+1):
    factorial.append(factorial[i-1]*i%mod)
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
print(power_func(2,n,mod)+1-cmb(n,a,mod)-cmb(n,b,mod))

Submission status: Wrong Answer

Solution code:
import scipy