Strassen

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

第一行一个正整数$t$表示数据组数（$1\le t \le 20$）。
每组数据包含一行三个正整数$n$，$a$，$b$（$1\le n\le 2^{32}$，$n$是$2$的幂，$1\le a\le 10^9$，$1\le b\le 10^9$）。

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

1
16 1 1

7872

2019 年百度之星·程序设计大赛 - 初赛四