你知道四千很喜歡玩Rabi-Ribi。這是個愛冒險的主角Erina，儘管被人們所憎恨，仍然深愛著這個世界的熱血遊戲。

這款遊戲最具特色也最有趣的地方便是boss戰裡的各種彈幕攻擊了。一隻boss擁有$M$種彈幕，在血量降為$0$前不斷選出一種彈幕攻擊Erina。四千雖然知道每種彈幕的躲法，常常卻因為無法及時判斷這是哪種彈幕而讓Erina受傷。有天四千發現，一隻boss的出招順序只跟她的前$K$次攻擊中選擇的彈幕有關。將boss的彈幕編號為$0, 1, \ldots, M-1$，並假設她在第$i (1 \leq i \leq K)$次攻擊選擇了彈幕$a_i$，則第$N$次的攻擊招式由下方的C函式給出：

long long ChooseAttack(long long N){
    if(N <= K){
        return a[N];
    }else{
        long long sum = 0;
        for(long long i=1; i<=K; i++){
            sum = sum + c[i]*ChooseAttack(N-i);
        }
        return sum % M;
    }
}

其中$\{c_i\}_{i=1}^K$是個全域long long陣列。不幸的是，四千發現他的C compiler壞了，因為不管等了多久，他的C程式都沒辦法算出ChooseAttack(100000)的值。現在他給你$M, K, N, \{a_i\}_{i=1}^K, \{c_i\}_{i=1}^K$，請你用ZJ的compiler幫他算出ChooseAttack(N)的值。