3 50 1000000000
532427493 109420729 661091328
153601170 540108444 608304270 456926383 634980384 433610157 386770743 293696730 489264211 798400685 383635028 672849809 10555083 789318352 544719600 931652304 675957900 495745091 586221237 747523639 104747519 924943847 848898023 96471036 288044038 337935042 914951677 25001140 885870909 922287102 909480189 844883197 638470852 36196047 658375770 610138803 188754584 508229145 124543111 985633215 862757369 727107622 794312960 866643218 204978363 505903444 935926006 358776559 315477793 955025157