站外数学题求助（目测橙~黄）

题目：
有$t$组数据，每个数据包含两个正数$n,m(1 \le m \le 10^9,1 \le n \le 10^{5*10^6})$求$(\sum_{i=1}^n i)\mod{m}$.
不要用FFT，NNT，FWT等，我看不懂
以及，我BDFS,STFW了，却只有诸如"关于 $\sum_{k=1}^n k^m$的一些结论","(k从1到n)∑k^m（其中m为正实常数）的近似公式（或者说无穷展开式）"等东西.