結果

問題 No.2807 Have Another Go (Easy)
ユーザー nouka28
提出日時 2024-07-12 23:22:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 382 ms / 3,000 ms
コード長 18,655 bytes
コンパイル時間 7,324 ms
コンパイル使用メモリ 335,564 KB
実行使用メモリ 38,036 KB
最終ジャッジ日時 2024-07-12 23:22:28
合計ジャッジ時間 18,824 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma region template
/*
    template made by nouka28
    last update 2024.7.7
*/
//include
#include<bits/stdc++.h>
using namespace std;
//atcoder
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
// using mint=atcoder::modint1000000007;
// using mint=atcoder::modint;
istream& operator>>(istream&is,mint &x){long long x_;is>>x_;x=x_;return is;}
ostream& operator<<(ostream&os,mint &x){os<<x.val();return os;}
//pragma
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//define
// #define int long long
#define pb push_back
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define ALL(x) begin(x),end(x)
#define LEN(x) (signed int)(x.size())
#define BIT(x,i) ((x)>>(i)&1)
//using
using u32=unsigned int;
using u64=unsigned long long;
using ull=unsigned long long;
using i32=signed int;
using i64=signed long long;
using ll=signed long long;
using f64=double;
using f80=long double;
using pi=pair<i32,i32>;
using pl=pair<i64,i64>;
using pd=pair<f80,f80>;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T>using VVV=V<V<V<T>>>;
template<class T>using VVVV=V<V<V<V<T>>>>;
template<class T>using VVVVV=V<V<V<V<V<T>>>>>;
template<class T>using pqmax=priority_queue<T>;
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;
using u128=__uint128_t;
using i128=__int128_t;
//io INT128
i128 i128_parse(string &s){i128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}
u128 u128_parse(string &s){u128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}
istream &operator>>(istream &is,i128 &x){string s;is>>s;x=i128_parse(s);return is;}
istream &operator>>(istream &is,u128 &x){string s;is>>s;x=u128_parse(s);return is;}
ostream &operator<<(ostream &os,i128 x){
    ostream::sentry s(os);
    if(s){u128 tmp=x<0?-x:x;char buffer[128];char *d=end(buffer);
        do{--d;*d="0123456789"[tmp%10];tmp/=10;}while(tmp!=0);
        if(x<0){--d;*d='-';}
        int len=end(buffer)-d;
        if (os.rdbuf()->sputn(d,len)!=len){os.setstate(ios_base::badbit);}
    }
    return os;
}
//const
const i64 LINF=0x1fffffffffffffff;
const i32 INF=0x3fffffff;
const i64 MOD=998244353;
const i64 MOD2=1000000007;
const f80 PI=3.1415926535897932384626433832795028841971;
const f80 DINF=numeric_limits<f80>::infinity();
const f80 EPS=1e-9;
const i64 di[]={0,1,0,-1,1,-1,1,-1};
const i64 dj[]={1,0,-1,0,1,1,-1,-1};
//function
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(i64 i=0;i<n;i++)
#define rep2(i,n) for(i64 i=0;i<n;i++)
#define rep3(i,a,b) for(i64 i=a;i<b;i++)
#define rep4(i,a,b,c) for(i64 i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(i64 i=n;i--;)
#define rrep2(i,n) for(i64 i=n;i--;)
#define rrep3(i,a,b) for(i64 i=b;i-->(a);)
#define rrep4(i,a,b,c) for(i64 i=(a)+((b)-(a)-1)/(c)*(c)i>=a;i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define SUM(...) accumulate(ALL(__VA_ARGS__),i64(0))
#define DSUM(...) accumulate(ALL(__VA_ARGS__),f80(0))
template<class T>bool chmin(T &x,const T&y){if(x>y){x=y;return true;}return false;}
template<class T>bool chmax(T &x,const T&y){if(x<y){x=y;return true;}return false;}
template<class T>i32 lob(const V<T>&arr,const T&v){return (i32)(lower_bound(ALL(arr),v)-arr.begin());}
template<class T>i32 upb(const V<T>&arr,const T&v){return (i32)(upper_bound(ALL(arr),v)-arr.begin());}
template<class T>constexpr auto min(T a,T b,T c){return min(a,min(b,c));}
template<class... T>constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
template<class T>constexpr auto max(T a,T b,T c){return max(a,max(b,c));}
template<class... T>constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
//io
struct SetUpIO{
    SetUpIO(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout<<fixed<<setprecision(15);
    }
}set_up_io;
//in
void scan(char &x){cin>>x;}
void scan(u32&x){cin>>x;}
void scan(u64 &x){cin>>x;}
void scan(i32 &x){cin>>x;}
void scan(i64 &x){cin>>x;}
void scan(string &x){cin>>x;}
void scan(mint &x){cin>>x;}
template<class T1,class T2>void scan(pair<T1,T2> &x){scan(x.first);scan(x.second);}
template<class T>void scan(V<T> &x){for(T &ele:x){scan(ele);}}
template<class T>void scan(deque<T> &x){for(T &ele:x){scan(ele);}}
template<class T,i32 size>void scan(array<T,size> &x){for(T &ele:x){scan(ele);}}
template<class T,i32 size>void scan(T (&x)[size]){for(T &ele:x){scan(ele);}}
void rd(){}
template<class Head,class... Tail>void rd(Head &head,Tail &...tail){scan(head);rd(tail...);}
#define CHR(...) char __VA_ARGS__;rd(__VA_ARGS__)
#define U32(...) u32 __VA_ARGS__;rd(__VA_ARGS__)
#define U64(...) u64 __VA_ARGS__;rd(__VA_ARGS__)
#define I32(...) i32 __VA_ARGS__;rd(__VA_ARGS__)
#define I64(...) i64 __VA_ARGS__;rd(__VA_ARGS__)
#define UINT(...) u32 __VA_ARGS__;rd(__VA_ARGS__)
#define ULL(...) u64 __VA_ARGS__;rd(__VA_ARGS__)
#define INT(...) i32 __VA_ARGS__;rd(__VA_ARGS__)
#define LL(...) i64 __VA_ARGS__;rd(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;rd(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size);rd(name);
#define VVEC(type,name,size1,size2) VV<type> name(size1,V<type>(size2));rd(name)
//out
void print(){putchar(' ');}
void print(bool x){printf("%d",x);}
void print(u32 x){printf("%u",x);}
void print(u64 x){printf("%llu",x);}
void print(i32 x){printf("%d",x);}
void print(i64 x){printf("%lld",x);}
void print(char x){printf("%c",x);}
void print(f64 x){printf("%.15f",x);}
void print(f80 x){printf("%.15Lf",x);}
void print(const string &x){for(auto&&i:x)print(i);}
void print(mint x){printf("%d",x.val());}
template<class T>void print(const V<T>&);
template<class T1,class T2>void print(const pair<T1,T2>&x){print(x.first);putchar(' ');print(x.second);}
template<class T>void print(complex<T>&x){if(x.real()>=0)print('+');print(x.real());if(x.imag()>=0)print('+');print(x.imag());print('i');}
template<class T>void print(const V<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const deque<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const unordered_set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i
    );}}
template<class T>void print(const multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const unordered_multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' '
    );print(*i);}}
template<class T1,class T2>void print(map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i
    );}}
template<class T1,class T2>void print(unordered_map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' '
    );print(*i);}}
template<class T, size_t size> void print(const array<T, size>& x){ print(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(' '); print(*i); 
    } }
template<class T,i32 size>void print(const T(&x)[size]){print(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ');*/print(*i);}}
template<class T>void print(const T&a){cout<<a;}
int out(){putchar('\n');return 0;}
template<class T>int out(const T&t){print(t);putchar('\n');return 0;}
template<class Head,class... Tail>int out(const Head&head,const Tail&...tail){print(head);putchar(' ');out(tail...);return 0;}
#ifdef LOCAL
void dbg(){putchar(' ');}
void dbg(bool x){printf("%d",x);}
void dbg(u32 x){printf("%u",x);}
void dbg(u64 x){printf("%llu",x);}
void dbg(i32 x){printf("%d",x);}
void dbg(i64 x){printf("%lld",x);}
void dbg(char x){printf("%c",x);}
void dbg(f64 x){printf("%.15f",x);}
void dbg(f80 x){printf("%.15Lf",x);}
void dbg(const string &x){for(auto&&i:x)dbg(i);}
void dbg(mint x){printf("%d",x.val());}
template<class T>void dbg(const V<T>&);
template<class T1,class T2>void dbg(const pair<T1,T2>&x){putchar('(');dbg(x.first);putchar(',');dbg(x.second);putchar(')');}
template<class T>void dbg(complex<T>&x){if(x.real()>=0)dbg('+');dbg(x.real());if(x.imag()>=0)dbg('+');dbg(x.imag());dbg('i');}
template<class T>void dbg(const V<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar(']'
    );}
template<class T>void dbg(const deque<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar
    (']');}
template<class T>void dbg(const set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i
    );}}putchar('}');}
template<class T>void dbg(const unordered_set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg
    (*i);}}putchar('}');}
template<class T>void dbg(const multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i
    );}}putchar('}');}
template<class T>void dbg(const unordered_multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(','
    );dbg(*i);}}putchar('}');}
template<class T1,class T2>void dbg(map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i
    );}}putchar('}');}
template<class T1,class T2>void dbg(unordered_map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar('
    ,');dbg(*i);}}putchar('}');}
template<class T, size_t size> void dbg(const array<T, size>& x){ putchar('[');dbg(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(','); 
    dbg(*i); } putchar(']');}
template<class T,i32 size>void dbg(const T(&x)[size]){/*putchar('[');*/dbg(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ')*/;dbg(*i);}/*putchar(']'
    );*/}
template<class T>void dbg(const T&a){cout<<a;}
int dbg2(){putchar('\n');return 0;}
template<class T>int dbg2(const T&t){dbg(t);putchar('\n');return 0;}
template<class Head,class... Tail>int dbg2(const Head&head,const Tail&...tail){dbg(head);putchar(' ');dbg2(tail...);return 0;}
#define debug(...) {dbg((string)(#__VA_ARGS__));dbg(":");dbg2(__VA_ARGS__);}
#else
#define debug(...) void(0)
#endif
//random
random_device rnd;mt19937 mt(rnd());const i64 MT_MAX=LINF;
uniform_int_distribution<i64> RAND(0,MT_MAX);
f64 randd(){return 1.0*RAND(mt)/MT_MAX;}
//random value [a,b]
i64 randint(i64 a,i64 b){return a+RAND(mt)%(b-a+1);}
//funtion2
#define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__}))
vector<vector<i64>> __MAKE_MAT__(vector<i64> v){
    if(v.empty())return vector<vector<i64>>(1,vector<i64>());
    i64 n=v.back();v.pop_back();vector<vector<i64>> ret,tmp=__MAKE_MAT__(v);
    for(auto e:tmp)for(i64 i=0;i<n;++i){ret.push_back(e);ret.back().push_back(i);}
    return ret;
}
//V',Pを返す。PはVを昇順に並べた時のidx
template<class T>
pair<vector<T>,vector<i32>> sortperm(vector<T> v){
    vector<pair<T,int>> sv;
    for(i32 i=0;i<(i32)v.size();i++){sv.push_back({v[i],i});}
    sort(sv.begin(),sv.end());vector<T> rv;vector<i32> p;
    for(auto[x,idx]:sv){rv.push_back(x);p.push_back(idx);}
    return {rv,p};
}
i64 pow(i64 a,i64 b){i64 x=1;while(b){if(b&1){x*=a;}a=a*a;b>>=1;}return x;}
bool isupper(char x){return('A'<=x&&x<='Z');}
bool islower(char x){return('a'<=x&&x<='z');}
char upper(char &x){if(isupper(x)){return x;}return x-'a'+'A';}
char lower(char &x){if(islower(x)){return x;}return x-'A'+'a';}
string upper(string s){for(auto&e:s)e=upper(e);return s;}
string lower(string s){for(auto&e:s)e=lower(e);return s;}
bool isdigit(char x){return('0'<=x&&x<='9');}
bool ingrid(int x,int y,int h,int w){return 0<=x&&x<h&&0<=y&&y<w;}
#pragma endregion
template<class mint>
struct FormalPowerSeries:vector<mint>{
    using vector<mint>::vector;
    using vector<mint>::operator=;
    using fps=FormalPowerSeries;
    using sfps=vector<pair<int,mint>>;
    fps& operator+=(const fps& g){
        if(g.size()>this->size())this->resize(g.size());
        for(int i=0;i<(int)g.size();i++)(*this)[i]+=g[i];
        return *this;
    }
    fps& operator+=(const mint& v){
        if(this->empty())this->resize(1);
        (*this)[0]+=v;
        return *this;
    }
    fps operator+(const fps& g)const{return fps(*this)+=g;}
    fps operator+(const mint& v)const{return fps(*this)+=v;}
    friend fps operator+(const mint& v,const fps& f){return f+v;}
    fps& operator+=(const int& v){*this+=mint(v);return *this;}
    fps operator+(const int& v){return fps(*this)+=v;;}
    friend fps operator+(const int& v,const fps& f){return f+v;}
    fps& operator-=(const fps& g){
        if(g.size()>this->size())this->resize(g.size());
        for(int i=0;i<(int)g.size();i++)(*this)[i]-=g[i];
        return *this;
    }
    fps& operator-=(const mint& v){
        if(this->empty())this->resize(1);
        (*this)[0]-=v;
        return *this;
    }
    fps operator-(const fps& g)const{return fps(*this)-=g;}
    fps operator-(const mint& v)const{return fps(*this)-=v;}
    friend fps operator-(const mint& v,const fps& f){return -(f-v);}
    fps& operator-=(const int& v){*this-=v;return *this;}
    fps operator-(const int& v){return fps(*this)-=v;}
    friend fps operator-(const int& v,const fps& f){return -(f-v);}
    fps operator-()const{return fps(*this)*=-1;}
    fps& operator*=(const mint& v){for(auto&e:*this)e*=v;return *this;}
    fps operator*(const mint& v)const{return fps(*this)*=v;}
    friend fps operator*(const mint& v,const fps& f){return f*v;}
    fps& operator*=(const int& v){*this*=mint(v);return *this;}
    fps operator*(const int& v)const{return fps(*this)*=v;}
    friend fps operator*(const int&v,const fps& f){return f*v;}
    fps& operator<<=(const int d){
        this->insert(this->begin(),d,0);
        return *this;
    }
    fps operator<<(const int d)const{return fps(*this)<<=d;}
    
    fps& operator>>=(const int d){
        this->erase(this->begin(),this->begin()+min((int)this->size(),d));
        return *this;
    }
    fps operator>>(const int d)const{return fps(*this)>>=d;}
    //fast
    fps& operator*=(const fps& g){
        *this=atcoder::convolution(*this,g);
        return *this;
    }
    
    //naive
    // fps& operator*=(const fps& g){
    //  this->resize(this->size()+g.size()-1);
    //  for(int i=(int)this->size()-1;i>=0;i--){
    //      for(int j=1;j<=(int)g.size();j++){
    //          if(i+j>=(int)this->size())break;
    //          (*this)[i+j]+=(*this)[i]*g[j];
    //      }
    //      (*this)[i]*=g[0];
    //  }
    //  return *this;
    // }
    fps operator*(const fps& g)const{return fps(*this)*=g;}
    fps inv(int d)const{
        fps g={(*this)[0].inv()};
        for(int k=1;k<d;k*=2){
            g=(2-*this*g)*g;
            g.resize(2*k);
        }
        g.resize(d+1);
        return g;
    }
    fps& operator/=(const fps& g){return *this=fps(*this*=g.inv()).pre(this->size());}
    fps& operator/=(const mint& v){for(auto&e:*this)e/=v;return *this;}
    fps operator/(const fps& g)const{return fps(*this)/=g;}
    fps operator/(const mint& v)const{return fps(*this)/=v;}
    
    fps quotient(const fps& g)const{
        if(this->size()<g.size())return fps();
        return (fps(this->rev()/g.rev()).pre(this->size()-g.size()+1)).rev();
    }
    fps reminder(const fps& g)const{return fps(*this-this->quotient(g)*g).pre(g.size()-1);}
    
    pair<fps,fps> quotient_reminder(const fps& g)const{
        pair<fps,fps> res;
        res.first=this->quotient(g);
        res.second=fps(*this-res.first*g).pre(g.size()-1);
        return res;
    }
    
    void shrink(){
        while(this->size()&&this->back()==mint(0))this->pop_back();
    }
    fps rev()const{fps g(*this);reverse(g.begin(),g.end());return g;}
    fps dot(fps g)const{
        fps res(min(this->size(),g.size()));
        for(int i=0;i<(int)res.size();i++)res[i]=(*this)[i]*g[i];
        return res;
    }
    fps pre(int d)const{
        fps res(begin(*this),begin(*this)+min((int)this->size(),d));
        if((int)res.size()<d)res.resize(d);
        return res;
    }
    fps& operator*=(const sfps& g){
        auto it0=g.begin();
        mint g0=0;
        if(it0->first==0){
            g0=it0->second;
            it0++;
        }
        for(int i=this->size()-1;i>=0;i--){
            for(auto it=it0;it!=g.end();it++){
                auto[j,gj]=*it;
                if(i+j>=this->size())break;
                (*this)[i+j]+=(*this)[i]*gj;
            }
            (*this)[i]*=g0;
        }
        return *this;
    }
    fps operator*(const sfps& g)const{return fps(*this)*=g;}
    fps& operator/=(const sfps& g){
        auto it0=g.begin();
        assert(it0->first==0&&it0->second!=0);
        mint g0_inv=it0->second.inv();
        it0++;
        for(int i=0;i<(int)this->size();i++){
            (*this)[i]*=g0_inv;
            for(auto it=it0;it!=g.begin();it++){
                auto[j,gj]=*it;
                if(i+j>=this->size())break;
                (*this)[i+j]-=(*this)[i]*gj;
            }
        }
        return *this;
    }
    fps operator/(const sfps& g)const{return fps(*this)/=g;}
    fps pow(long long d,const fps& g)const{
        fps res={1},pow2=*this;
        while(d>0){
            if(d&1)res=(res*pow2).reminder(g);
            pow2=(pow2*pow2).reminder(g);
            d>>=1;
        }
        return res;
    }
    fps derivative()const{
        fps res;
        for(int i=1;i<(int)this->size();i++)res.push_back((*this)[i]*i);
        return res;
    }
    fps integral()const{
        fps res={0};
        for(int i=0;i<(int)this->size();i++)res.push_back((*this)[i]/(i+1));
        return res;
    }
    fps log(int d)const{
        return fps(this->derivative()*this->inv(d)).integral().pre(d);
    }
    fps exp(int d)const{
        fps g={1};
        for(int k=1;k<d;k*=2){
            g=g*(*this+1-g.log(2*k));
            g.resize(2*k);
        }
        return g.pre(d);
    }
    fps pow(long long k,int d)const{
        if(k==0){
            fps res(d,mint(0));
            if(d)res[0]=1;
            return res;
        }
        int i0=0;
        while(i0<(int)this->size()&&(*this)[i0]==mint(0))i0++;
        if(i0==(int)this->size())return fps(d,mint(0));
        mint c0=(*this)[i0];
        fps fs=(*this>>i0)/c0;
        if(i0>=(d+k-1)/k)return fps(d,mint(0));
        int ds=(int)(d-k*i0);
        fps gs=fps(mint(k)*fs.log(ds)).exp(ds);
        fps g=fps(gs*c0.pow(k))<<(int)(k*i0);
        return g;
    }
    friend istream& operator>>(istream& is,fps&f){
        for(auto&e:f)cin>>e;
        return is;
    }
    friend ostream& operator<<(ostream& os,const fps& f){
        if((int)f.size()==0)os<<0;
        else{
            for(int i=0;i<(int)f.size();i++){
                os<<f[i].val();
                if(i<(int)f.size()-1)os<<" ";
            }
            return os;
        }
        return os;
    }
};
using fps=FormalPowerSeries<mint>;
using sfps=vector<pair<int,mint>>;
mint f[1000009];
int main(){
    INT(n,m,k);
    VEC(int,c,k);
    //( -1+x^2+2*x^3+3*x^4+4*x^5 ) / ( -1+x+x^2+x^3+x^4+x^5+x^6 )
    fps f1={-1,0,1,2,3,4},g={-1,1,1,1,1,1,1};
    f1*=g.inv(2*n+10);
    // cout<<f1<<endl;
    f[0]=1;
    rep(i,2*n+1){
        rep(j,1,7){
            f[i+j]+=f[i];
        }
    }
    // rep(i,2*n+1)cout<<f[i]<<" ";
    // cout<<endl;
    rep(i,k){
        mint ans=f[c[i]]*f1[2*n-c[i]+5];
        ans+=f[n+c[i]]*f1[n-c[i]+5];
        ans-=f[c[i]]*f[n]*f1[n-c[i]+5];
        out(ans);
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0