题目描述

在本题中，我们只有两种方法计算两个$n×n$的矩阵的乘积，第一种为定义法，需要$n ^ 3$次乘法和$(n−1)n ^ 2$次加法。第二种为$Strassen$分治法，仅当$n$为偶数时可以使用，需要$18(n/2) ^ 2$次加法以及再计算7次大小为$(n/2)×(n/2)$的矩阵的乘积。这$7$次更小矩阵的乘积也可以选择两种方法之一计算。现假设计算机计算一次加法需要$a$单位时间，计算一次乘法需要$b$单位时间，其他任何操作不花费时间，问计算两个$n×n$的矩阵的乘积至少需要多少时间。输出答案模$10 ^ 9+7$的余数。

输入格式

第一行一个正整数$t$表示数据组数$（1≤t≤200）$。
每组数据包含一行三个正整数$n，a，b（1≤n≤ 2 的32次方，n是2的幂，1≤a≤10^9，1≤b≤10^9）$。

输出格式

每组数据输出一行，包含一个整数表示答案模$10^9+7$的余数。

样例

样例输入

1   
16 1 1   

样例输出

7872   

数据范围与提示

正解 大数模板 或 int128