3 50 1000000000
181954 935253 259385
381347433 313376503 912953280 499840013 88516433 99254877 720441732 67413612 275283313 268794656 202722190 931997170 265474627 562954768 423720160 958872509 863770959 146495564 664024506 584919501 174249410 888191220 759449466 198926131 939433890 243581202 452291975 585375117 196728220 724635790 677159299 41082092 299107053 190710673 953241989 24060353 596939605 445165598 304907139 443987167 327821194 872022085 382486960 953646643 511287601 97035206 705137671 850724165 895287235 907554423