输入

2 1000
1000000007 1000000009

输出

1000000328000052554005481512418470335926982726072815502069603213159355156546075303616833177315722321230547320073304515542197163179708685295600136061536455198253335029816954913596911127529851228616605927616413646346721876239562908743960015876894896130773236557041036546346552085794082140837788592093520195652806581991230126812866647556793990025604596250357477558916667965507347981202109994543616449