XXX国有一个有趣的数学游戏,叫做"?逋泼診",它是一个N阶递推问题,递推关系由一个多项式表示

       0 (n <= 0)
  An = x (n = 1)
  	B1*An-1 + B2*An-2 +...+ Bk*An-k  

其中Bi是一组常系数,Ai是要求的数列,k是这个递推式的阶数,x是第一项的值. 一般XXX星球问候朋友的时候总不忘记问这个问题,给你x,k,Bi(1 < = i < = k) An是多少? 例如:x = 1 , k = 2 , B1 = 1 , B2 = 1 , n = 6 回答应该是8 (数列顺序是1,1,2,3,5,8)

每个case第一行 三个整数x,k ,n ( 0 < x < 10 , 0 < k <= 11 , 1 < = n < = 2000000000 ) 第二行k个数,表示:B1,B2...Bk (1 < = Bi < = 5 ) 0 0 0 表示结束

一个整数,由于答案会很大,所以请输出 An MOD 2008