#pragma once
#include<cassert>
#include<vector>usingnamespacestd;#include"../math/constexpr-primitive-root.hpp"template<typenamefps>fpsmultiplicative_convolution_mod_p(constfps&a,constfps&b,intp){assert((int)a.size()==p);assert((int)b.size()==p);usingmint=typenamefps::value_type;intr=constexpr_primitive_root(p);vector<int>exp(p-1),log(p);exp[0]=1;for(inti=1;i<p-1;i++)exp[i]=1LL*exp[i-1]*r%p;for(inti=0;i<p-1;i++)log[exp[i]]=i;fpss(p-1),t(p-1);for(inti=0;i<p-1;i++)s[i]=a[exp[i]],t[i]=b[exp[i]];fpsu=s*t;for(inti=p-1;i<(int)u.size();i++)u[i%(p-1)]+=u[i];fpsc(p);for(inti=1;i<p;i++)c[i]=u[log[i]];mintsa=accumulate(begin(a),end(a),mint{});mintsb=accumulate(begin(b),end(b),mint{});c[0]=sa*b[0]+sb*a[0]-a[0]*b[0];returnc;}