2014
02-12

# Linux Kernel Version

Samuel is fed up with Microsoft Windows system. Instead of xp he chose to install Linux Fedora 10 in his own desktop. But Linux has various distributions with different kernel versions. Some kernels are not stable. Of course,the unstable ones is not of Samuel’s choice. Samuel is never tired of reinstalling Linux,because he always wants to try the latest release version on his computer. So Samuel needs to know the kernel’s version before he downloads the distribution version.
Here is an easy problem for you,tell Samuel which distribution he should choose to reinstall.
To make the problem easier,suppose each Linux kernel version mark is made up by a string like the format:”r.x.y”Here r represents the major version number,x will be even(stable) or odd(beta version not stable,need to be developed),y represents the time the kernel has been corrected. For instance,the kernel whose number is 2.6.7 is a stable version. However,2.5.11 is not due to the number the letter x represents is odd.
As for he problem which one is the latest kernel,you can also refer to version number. When compared two version,you should first compare the r1 and r2, if r1>r2 version 1 is the latest version. If r1=r2,you need to compare x1 and x2,if x1>x2 that means the version 1 is the latest. If x1=x2,then you need to compare y1 and y2,version 1 is the newest one only if y1>y2..Not clear about my English explanation,you can see the HDOJ 1976,it has a Chinese one.

The input will consist 2 major parts:
Test cases t.
Each of test case is made up of 2 minor parts:
1.The number of available distributions
2.Name of the distribution(a string,no white blanks)
3.The kernel version(also a string in the format r.x.y without any blanks)
I guarantee there is no test case has the same distribution name but with different kernel version nor the same kernel version but with the different distribution name. All the information in the same test cases is totally different.

The input will consist 2 major parts:
Test cases t.
Each of test case is made up of 2 minor parts:
1.The number of available distributions
2.Name of the distribution(a string,no white blanks)
3.The kernel version(also a string in the format r.x.y without any blanks)
I guarantee there is no test case has the same distribution name but with different kernel version nor the same kernel version but with the different distribution name. All the information in the same test cases is totally different.

2
3
SUSE 2.6.5
Fedora 2.6.7
Ubuntu 2.6.6
4
RedFlag 2.4.5
CentOS 2.5.6
Fedora 2.4.3
Debian 2.5.7
(In reality,the kernel version may not be so. The numbers are made up by myself.)

The latest distribution Samuel will choose is Fedora.
The latest distribution Samuel will choose is RedFlag.

#include <stdio.h>
#include <cstring>
#define mod 9999997
long long tmp[3][3],ans[3][3],a[3][3];
void mul(long long a[][3],long long b[][3])
{
for(int i=1; i<=2; i++)
for(int j=1; j<=2; j++)
{
tmp[i][j]=0;
for(int k=1; k<=2; k++)
tmp[i][j]+=a[i][k]*b[k][j];
if(tmp[i][j]>=mod) tmp[i][j]%=mod;
}
memcpy(a,tmp,sizeof(tmp));
}
void pow(long long ans[][3],long long b[][3],int n)
{
ans[1][1]=ans[2][2]=1;
ans[1][2]=ans[2][1]=0;
while(n)
{
if(n&1) mul(ans,b);
mul(b,b);
n>>=1;
}
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
memset(ans,0,sizeof(ans));
a[1][1]=3;
a[1][2]=a[2][2]=1;
a[2][1]=0;
pow(ans,a,n);
printf("%d\n",ans[1][2]%mod);
}
return 0;
}