Problem 2E. 演算资本积累模型

时间限制：1s

空间限制：64MB

题目背景

在经济学中，资本积累是指投资和储蓄对于经济增长的影响。实物投资（Real investment），是指以实物作为出资方式的投资。即投资者将资金用于建造购置固定资产和流动资产，直接用于生产经营，并以此获得未来收益的投资。金融投资（Financial investment），又称“证券投资”，是指投资者以获得未来收益为目的，预先垫付一定的资金并获得金融资产的投资。金融投资是经济主体为获取预期收益或股权，用资金购买股票、债券等金融资产的投资活动。

题目描述

考虑一个简化的经济模型，其中有两种资本：实物资本和金融资本。这两种资本在每个时间步都会根据以下线性差分方程进行更新：
\[ \begin{cases} K[t] &= a \cdot K[t-1] + b \cdot F[t-1]\\ F[t] &= c \cdot K[t-1] + d \cdot F[t-1] \end{cases} \]
其中初始值：
\[ K[0]=F[0]=1 \]
在这些方程中，\(K[t]\)表示时间步\(t\) 上的实物资本，\(F[t]\)表示时间步\(t\) 上的金融资本。\(a\)、\(b\)、\(c\)、\(d\)是常数，表示资本线性差分方程的系数。现在，你需要编写一个程序来模拟这个经济模型的演化。给定初始的实物资本\(K[0]\)和金融资本\(F[0]\)，以及常数\(a\)、\(b\)、\(c\)、\(d\)。

由于计算结果可能很大，请计算并输出在给定时间步\(T\) 时实物资本\(K[T]\)和金融资本\(F[T]\)的值分别对\(10^9+7\) 取模后的结果。

输入格式

• 共一行5个正整数。分别是\(a\)、\(b\)、\(c\)、\(d\) 和整数\(T\)。
• \(a、b、c、d\) 表示资本线性差分方程的权重系数。 \(T\) 表示模拟的时间步数。

输出格式

对于时间步\(t=T\)，在一行上输出实物资本\(K[T]\)和金融资本\(F[T]\)的值分别的对\(10^9+7\)取模后的结果。

样例输入1

2 1 1 1 1

样例输出1

3 2

样例解释

\(K[1]=(2\times1+1\times1)\%(1e9+7)=3\)，\(F[1]=(1\times1+1\times1)\%(1e9+7)=2\)

样例输入 2

6 6 4 3 110

样例输出 2

364921629 735281804

样例输入 3

939 575 671 194 498000000000

样例输出 3

575278122 746904893

数据范围及限制

对于 \(60\%\) 的数据，\(1\le T\le 5\times10^4 ;a,b,c,d\in[1,10],\)

对于 \(100\%\) 的数据，\(1\le T\le 1\times10^{14};a,b,c,d\in[1,1000]\)。