题目链接
在本题中，我们只有两种方法计算两个n×n的矩阵的乘积，第一种为定义法，需要n^3次乘法和(n−1)n^2次加法。第二种为Strassen分治法，仅当n为偶数时可以使用，需要18 * (n/2) * (n/2)次加法以及再计算7次大小为(n/2)×(n/2)的矩阵的乘积。这7次更小矩阵的乘积也可以选择两种方法之一计算。现假设计算机计算一次加法需要a单位时间，计算一次乘法需要b单位时间，其他任何操作不花费时间，问计算两个n×n的矩阵的乘积至少需要多少时间。输出答案模1e9 + 7的余数。
Input
第一行一个正整数t表示数据组数（1≤t≤20）。
每组数据包含一行三个正整数n，a，b（1≤n≤2^32，n是2的幂，1≤a≤1e9，1≤b≤1e9）。
Output
每组数据输出一行，包含一个整数表示答案模109+7的余数。
题目链接
Rock-paper-scissors is a zero-sum hand game usually played between two people, in which each player simultaneously forms one of three shapes with an outstretched hand. These shapes are “rock”, “paper”, and “scissors”. The game has only three possible outcomes other than a tie: a player who decides to play rock will beat another player who has chosen scissors (“rock crushes scissors”) but will lose to one who has played paper (“paper covers rock”); a play of paper will lose to a play of scissors (“scissors cut paper”). If both players choose the same shape, the game is tied and is usually immediately replayed to break the tie.