#include "math/NTT2d.hpp"
vector<vector<mint>>NTT2d(const vector<vector<mint>>&s,const vector<vector<mint>>&t){ int sh=s.size()+t.size()-1; int sw=s[0].size()+t[0].size()-1; int h=1,w=1; while(h<sh)h*=2; while(w<sw)w*=2; fps<mint>f(h*w),g(h*w); vector<vector<mint>>res(sh,vector<mint>(sw)); rep(i,s.size())rep(j,s[0].size()){ f[i*w+j]=s[i][j]; } rep(i,t.size())rep(j,t[0].size()){ g[i*w+j]=t[i][j]; } f*=g; rep(i,sh)rep(j,sw){ res[i][j]=f[i*w+j]; } return res; }
#line 1 "math/NTT2d.hpp" vector<vector<mint>>NTT2d(const vector<vector<mint>>&s,const vector<vector<mint>>&t){ int sh=s.size()+t.size()-1; int sw=s[0].size()+t[0].size()-1; int h=1,w=1; while(h<sh)h*=2; while(w<sw)w*=2; fps<mint>f(h*w),g(h*w); vector<vector<mint>>res(sh,vector<mint>(sw)); rep(i,s.size())rep(j,s[0].size()){ f[i*w+j]=s[i][j]; } rep(i,t.size())rep(j,t[0].size()){ g[i*w+j]=t[i][j]; } f*=g; rep(i,sh)rep(j,sw){ res[i][j]=f[i*w+j]; } return res; }