5 43 1000000000
375527796 961078091 953428839 801899660 546442687
373120007 241405412 582765917 166433113 105078783 329787204 510387884 946975162 289286028 504988124 890614398 536209502 510927508 165349111 827210709 763265114 217161798 804231401 824824786 90590833 166277997 193305096 392930192 71169706 901267505 687908055 260120515 857491155 482184863 826350089 58130364 59155963 961672653 645037479 584957930 495989064 338025469 381292792 6464103 643535150 970167938 485745025 605823160