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


public class Main{
    static BigInteger a=new BigInteger("0");
    static BigInteger b=new BigInteger("0");
    static BigInteger  cal(BigInteger n)
    {
        return n.multiply(n).multiply(n).multiply(b).add( n.multiply(n).multiply(n.subtract(BigInteger.ONE)).multiply(a));
    }
    static  BigInteger  add(BigInteger n)
    {
        return n.multiply(n).multiply(a).multiply(BigInteger.valueOf(18));
    }
    static BigInteger fun(BigInteger n)
    {
        if(!n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO))
        {
            return b;
        }
        BigInteger temp1=add(n.shiftRight(1)).add(fun(n.shiftRight(1)).multiply(BigInteger.valueOf(7)));
        BigInteger temp2=cal(n);
        if(temp1.compareTo(temp2)>0)
            return temp2;
        return temp1;

    }
    public static void main(String[] args){
        BigInteger n;
        int t;
        
        Scanner cin=new Scanner(System.in);
        t=cin.nextInt();
        for(int i=1;i<=t;i++)
        {    n=cin.nextBigInteger();
        a=cin.nextBigInteger();
        b=cin.nextBigInteger();
        System.out.println(fun(n).mod(BigInteger.valueOf(1000000007l)));
            
        }
    
    }
}