第一次做这种少人做的题目，感觉好爽啊~~~ 这个题目的解法借鉴了Matrix67大神的好文章：
10种经典的矩阵解法 这里讲得很好，我用的是矩阵的经典7，专门用来借线性递推的。
再结合矩阵的快速幂，这题无疑是小细节要注意注意了！
#include<iostream>
#define MAXN 101
#define mod 10000
#define ull unsigned long long
using namespace std;struct Matrix
{ull ans[MAXN][MAXN];
};int k,T,n;void Matrix2( Matrix &a,Matrix &b )
{Matrix now;memset( now.ans,0,sizeof(now.ans) );int i,j,p;for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){now.ans[i][j]=0;for( p=1;p<=n;p++ )now.ans[i][j]=( now.ans[i][j]+a.ans[i][p]*b.ans[p][j] )%mod;} a=now;
}
void MatrixPow( int k,Matrix &pre )
{Matrix now1=pre;Matrix now2=pre;if( k<=1 )return;else if( k%2==0 ){MatrixPow( k>>1,now1 );Matrix2( now1,now1 );}else if( k%2==1 ){MatrixPow( k-1,now1 );Matrix2( now1,now2 );}pre=now1;
}int main( )
{ull A[MAXN];ull B[MAXN];while( scanf( "%d",&k )!=EOF ){if( !k )break;n=k;int i,j,p;for( i=0;i<k;i++ )scanf( "%llu",&A[i] );for( i=1;i<=k;i++ )scanf( "%llu",&B[k-i+1] );scanf( "%d",&T );Matrix Ans;memset( Ans.ans,0,sizeof(Ans.ans) );for( i=1;i<=k;i++ )if( i==k )for( j=1;j<=k;j++ )Ans.ans[k][j]=B[j];elseAns.ans[i][i+1]=1;if( T<k )printf( "%llu\n",A[T] );else{MatrixPow( T-k+1,Ans );ull sum=0;for( p=1;p<=k;p++ )sum=(sum+Ans.ans[k][p]*A[p-1])%mod;printf( "%llu\n",sum%mod );}}return 0;
}