import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static BigInteger dfs(BigInteger n,BigInteger a,BigInteger b)
    {
        if(n.equals(BigInteger.valueOf(1)))
        {
            return b;
        }
        BigInteger ans=BigInteger.valueOf(0),res=BigInteger.valueOf(0);
        BigInteger aa=n.pow(3);
        aa=aa.multiply(b);
        BigInteger bb=n.pow(2);
        bb=bb.multiply(n.subtract(BigInteger.valueOf(1)));
        bb=bb.multiply(a);
        ans=aa.add(bb);
        if(n.mod(BigInteger.valueOf(2)).equals(BigInteger.valueOf(0))) {
            BigInteger k=n.divide(BigInteger.valueOf(2));//n/2
            res=k.pow(2);
            res=res.multiply(BigInteger.valueOf(18).multiply(a));
            res=res.add(BigInteger.valueOf(7).multiply(dfs(k,a,b)));
            if(res.compareTo(ans)<0)
                ans=res;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int t;
        BigInteger n,a,b;
        t=in.nextInt();
        BigInteger gg=BigInteger.valueOf(1000000007);
        while(t!=0)
        {
            n=in.nextBigInteger();
            a=in.nextBigInteger();
            b=in.nextBigInteger();
            BigInteger kk=dfs(n,a,b);
            System.out.println(kk.mod(gg));
            t--;
        }
    }
}