Description

神犇LYD虐完HEOI之后给傻×XLk出了一题： SHY是某国的公主，平时的一大爱好是读诗...(中间略)...结果mod p就可以了

简明题意 给定 k,a,n,d,p f(i)=1^k+2^k+3^k+......+i^k g(x)=f(1)+f(2)+f(3)+....+f(x) 求(g(a)+g(a+d)+g(a+2d)+......+g(a+nd))mod p

对于所有数据 1<=k<=123 0<=a,n,d<=123456789 p==1234567891

Format

Input

第一行数据组数，(保证小于6) 以下每行四个整数 k,a,n,d

Output

每行一个结果。

Samples

5
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

5
5
5
5
5