Count Sequences

You are given $2$ integers $N$ and $M$. For each $x$ such that $0 \leq x < M$, count the number of non-negative integer sequences $A_1,A_2,\ldots,A_M$ such that: - $\sum\limits_{i=1}^M A_i = N$ - $\prod\limits_{i=1}^M i^{A_i} = x \pmod {M}$ Since the answer can be large, output the answer modulo $10^9+7$. ### Input - First line will contain $T$, number of test cases. Then the test cases follow