$O(M)$ 找规律，递推

首先看数据范围，我们需要先预处理出 M 层塔分别需要多少卡牌。设 $a_i$ 表示 $i$ 层塔的卡牌数量

找规律可以发现：

• 第一层：$0$ 个三角形，加最左最右两条边。
• 第二层：$1$ 个三角形，加最左最右两条边。
• 第三层：$2$ 个三角形，加最左最右两条边。
• ...
• 第 $i$ 层：$i-1$ 个三角形，加最左最右两条边。

所以 $a_i = a_{i - 1} + (i - 1) * 3 + 2$

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000007;
const int N = 1e6 + 10;
long long a[N];

int main(){
	for(int i = 1; i <= 1e6; ++i){
		a[i] = (i - 1 + a[i - 1] + i * 2) % mod;
	}
	int t, n;
	cin >> t;
	while(t--){
		cin >> n;
		cout << a[n] << endl; 
	}
	return 0;
}