2017 省賽選撥 想打架嗎？算我一個！所有人，都過來！(3) 遞推 斐波拉數列的應用...

想打架嗎？算我一個！所有人，都過來！(3)

Submit Page????Summary????Time Limit:?2 Sec?????Memory Limit:?128 Mb?????Submitted:?28?????Solved:?9????

---

Description

現在《爐石傳說》這款卡牌游戲已經風靡全球。2015年加入環境的“黑石山的火焰”擴展帶來了一個新套牌的核心卡片“恐怖的奴隸主”，而這套統治游戲的套牌叫做“奴隸戰”。“恐怖的奴隸主”的登場音效“想打架嗎？算我一個！”一定在所有這個時代的《爐石傳說》玩家心里留下來難以磨滅的印象。
“恐怖的奴隸主”是一個有3點生命值的生物，當其在場上受到非致命傷害時（如3點生命值的奴隸主受到1點或2點傷害時，或者2點生命值的奴隸主受到1點傷害時）會召喚一個新的3點生命值的“恐怖的奴隸主”，受到致命傷害（傷害大于等于現有生命值）時則會直接死去。另外一類卡片可以使全部生物造成1點傷害（降低1點生命），被稱為“旋風斬效果”。因此“恐怖的奴隸主”，在場上經過多次“旋風斬效果”就可能由一個變成很多個，同時發出那個令人恐懼的聲音“所有人，都過來！”。
另一方面，《爐石傳說》規定，場上最多存在7個生物，這極大地限制了“恐怖的奴隸主”“越生越多”。當一次“旋風斬效果”發生時，優先處理受到非致命傷害的“恐怖的奴隸主”，召喚新的“恐怖的奴隸主”，直到生物數量達到7個不再繼續召喚新的“恐怖的奴隸主”，然后清除掉生命值降為0或0以下的“恐怖奴隸主”。如場上有7個生命值為1的“恐怖的奴隸主”，則一次“旋風斬效果”后場上有0個“恐怖的奴隸主”。又如，場上有6個生命值為3的“恐怖的奴隸主”，則一次“旋風斬效果”后場上有6個2點生命的“恐怖的奴隸主”以及1個3點生命的“恐怖的奴隸主”。又如，場上有4個1點生命的“恐怖的奴隸主”以及2個2點生命的“恐怖的奴隸主”，則一次“旋風斬效果”后場上有2個1點生命的“恐怖的奴隸主”以及1個3點生命的“恐怖的奴隸主”。
在本系列題目2中我們已經知道了如何計算多個“恐怖的奴隸主”在經歷n次旋風斬效果后會剩下多少。現在游戲出現了bug，場上奴隸主的個數不再受到7個的上限限制了。場上剩下了一些1點生命，一些2點生命，一些3點生命的奴隸主，現在問這些奴隸主經過n次旋風斬效果，場面會變成什么樣子。

?

Input

有多組數據。
每組數據一行，hp1,hp2,hp3,n(0<=hp1,hp2,hp3<=10^9,0<=n<=10^6)
分別代表1點生命，2點生命，3點生命的奴隸主個數，以及之后旋風斬次數。

?

Output

每組用一行輸出最終總的奴隸主個數（結果對1000000007取模），格式見樣例。

?

Sample Input

1 1 1 3
3 3 3 2

Sample Output

10
18

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define ll long long
using namespace std;
#define mod 1000000007
#define maxn 1000005
ll fab[maxn];
void init(){fab[0] = 1;fab[1] = 1;for(int i=2;i<N;i++){fab[i] = (fab[i-1]+fab[i-2])%mod;}
}
int main()
{init();LL a,b,c;int k;while(scanf("%lld%lld%lld%d",&a,&b,&c,&k)!=EOF){LL ans1 = fab[k-1]*b%mod;LL ans2 = fab[k]*c%mod;printf("%lld\n",((ans1+ans2)*2)%mod);}return 0;
}

?