化學(xué)不及格的Matrix67無奈選擇了文科。他必須硬著頭皮準(zhǔn)備一次又一次的文科考試。
在這一學(xué)期一共有n次文科考試，考試科目有4種，分別為政治、歷史、地理和綜合。每次考哪一科是不定的，因此在考試前Matrix67不知道應(yīng)該 去復(fù)習(xí)哪一科的功課。他希望能預(yù)測出下一次可能考的科目。于是，他收集到了以往的文科考試的資料。從以往的考試中，他發(fā)現(xiàn)了這樣幾個規(guī)律：
1.如果這次考的是政治，那么下一次一定會考?xì)v史；
2.如果這次考的是綜合，那么下一次一定會考地理；
3.如果這次考的是歷史，那么下一次要么考政治，要么考地理；
4.如果這次考的是地理，那么下一次要么考?xì)v史，要么考綜合。
Matrix67已經(jīng)知道，本學(xué)期的第一次考試科目為政治。他打算擬定一個可以應(yīng)對所有可能情況的應(yīng)考復(fù)習(xí)計劃。因此，他想知道，整個學(xué)期有多少種可能的考試科目安排滿足以上規(guī)律。你能幫他算出來嗎？
一個正整數(shù)n，代表本學(xué)期總的考試次數(shù)。（輸入數(shù)據(jù)保證n<=10000）
一個正整數(shù)，表示符合規(guī)律的科目安排方案的總數(shù)。
考慮到這個結(jié)果可能會很大，因此你只需要輸出它mod 7654321的值即可。
5
5