5 50 1000000000
7 4 9 10 10
824847612 422939105 720391250 331736684 204444049 875665059 159107039 407581671 29178896 397787285 616450307 200419648 886281643 959388781 862513780 909102914 261957153 201210658 899586993 287999060 392642984 378438757 118589392 616656492 50837030 977341839 819761255 490759024 437370464 864136323 394487422 918744528 602001007 75452602 715128838 458462648 64201495 609777910 529736908 378246582 556018771 829250757 908525665 76773917 58877882 331181924 38976751 246091534 556206591 398677024