**Towers (in how many ways tower of size n can be formed using k blocks (infinite of each type) )

Towers 

One day John had to take care of his little nephew Jim. He was very busy, so he gave Jim a big bag full of building bricks. The bricks are of various heights: at most 15 different heights. For each height, the bag contains infinitely many bricks. 

Now, Jim’s task is to build every possible tower of height  from the given bricks. Bricks are stacked vertically only and stand in an upright position. Two towers are different if their brick height sequences are different. 
Jim is good at building towers and can build one tower in exactly 2 minutes, regardless of its height. John wants to know the time Jim requires to build all possible towers.

Input Format 
There are  lines of input. First line contains an integer, , the height of tower to be built. Second line contains another integer, , which represents different heights of bricks available in the bag. Third line contains  distinct integers representing the available heights.

Output Format 
In one line print the number of minutes Jim requires to build all possible towers. As this number can be very large, print the number modulo .

Constraints 
 
 
All heights will be unique. 
Height of each brick will lie in range [1, 15].

Sample Input#00

10
1
1

Sample Output#00

2

Explanation#00: There is exactly one type of brick, so there is exactly one tower of height 10. Building any tower takes 2 minutes, so the answer is 2.

Sample Input#01

5
2
2 3

Sample Output#01

4

Explanation #01: There are two types of bricks. There are two different towers of height 5 which can be build from these types of bricks:  and . They are different, because the sequence of bricks in them is different. Building any tower takes 2 minutes, so the answer is .

Sample Input#03

19
2
4 5

Sample Output#03

8

Explanation #03: There are two types of bricks. Jim can build 4 different towers of height  from these bricks: , ,  and . Building any tower takes 2 minutes, so the answer is .

============================editorial=========================

In the editorial I omit the fact that we have to count the time needed to build all towers - we will count here just the number of different towers and to get the result, you have to multiply this number by 2

Simpler problem first

There is a restriction, that every bricks is of height at most 15 and  is at most . Lets first try to solve a simpler problem and assume that there are only bricks of height 1 or 2 and .

Let  be the number of different towers of height  which can be build of given bricks. In our simpler problem we have:

, because there is only one tower of height 1 consisting of one bricks of height 1

, because there are exactly two towers of height 2 - one consisting of two bricks of height 1 and the other consisting of one brick of height 2

We can now give a recursive definition for  when :

because we can get one unique tower of height  by placing a brick of height 1 on any tower of height  and one unique tower of height also  by placing a brick of height 2 on any tower of height .

If we compute  bottom-up (like in dynamic programming) rather than using recursion explicitly, we can do it in  time which is fine if  is not as big as in the problem statement.

Removing heights restriction

Lets remove the first restriction, so we have to deal now with bricks of at most 15 different heights (from 1 to 15).

Let  indicates whether we have a brick of height :

then the general recursion equation is:

 for 

 for 

Solving the original problem

The last thing that we have do deal with is the really big  - up to . We will do it defining the recursive equation as a matrix multiplication problem and solve it using fast matrix exponentiation.

Lets assume that we've computed  for  using dynamic programming and let  be a  matrix defined as follows:

Let  be the following vector:

if we multiply  we get:

and we can return  from here, so in order to compute  for  we can compute:

which can be written in the following form, because matrix multiplication is associative:

and we can compute -th power of a matrix of size  is  using fast exponentiation by squaring and in our problem we have  and  which is perfectly fine in terms of time limits. One speedup here can be to do exponentiation iteratively rather than recursively.

=============================code========================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

lli dp[16];

vector<int> v;

lli n;

int k;

lli mod= 1000000007;

int has[20];

lli mulmod(lli b,lli a,lli m)

 {

    return (1ll*b*a)%m;

  if(a==1) return b;

         

  else if(a==0) return 0;

  else 

  {

  if(a%2==1)

    {

    return (1ll*(mulmod(b,a/2,m)*2)%m+b)%m;

 

  }

  else return (1ll*(mulmod(b,a/2,m)*2)%m);

 

}

 }

class expo

{

 public :

 lli sz=15;

 void mul(lli mat1[15][15],lli mat2[15][15],lli  ret[15][15],lli m)

 {

  for(lli i=0;i<sz;i++)

   {

    for(lli j=0;j<sz;j++)

       {

        ret[i][j]=0;

        for(lli k=0;k<sz;k++)

            {

            ret[i][j]=(ret[i][j]+mulmod(mat1[i][k],mat2[k][j],m))%m;

            while(ret[i][j]<0)

                {

                ret[i][j]+=m;

}

ret[i][j]%=m;

         

}

   

}

 

 }

 }

void rais(lli base[][15], lli n,lli ans[][15],lli mod)

 {

 //  cout<<"rase "<<n<<endl;

    for(int i=0;i<15;i++)

    {

    for(int j=0;j<15;j++)

        {

 if(i!=j)ans[i][j]=0;

 else ans[i][j]=1; 

     

}

}

   lli temp[15][15];

      while(n>0)

    {

    if(n%2)

         {

          mul(ans,base,temp,mod);

          for(lli i=0;i<15;i++)

                {

                for(lli j=0;j<15;j++)

                         {

                          ans[i][j]=temp[i][j];

               

 }

         

  }

     

 }

 mul(base,base,temp,mod);

       for(lli i=0;i<15;i++)

                {

                        for(lli j=0;j<15;j++)

                         {

                          base[i][j]=temp[i][j];

               

 }

         

  }

   

    n/=2;

  }

 }

lli fibo(lli n,lli mod)

 {

  lli base[15][15];

  memset(base,0,sizeof base);

  // filling first column 

 

  for(int j=0;j<15;j++)

      {

      if(has[j+1]==1)

           {

            base[j][0]=1;

 }

}

// filling rest 

for(int i=0;i<14;i++)

 {

  base[i][i+1]=1;

 }

 

 

 

  lli ans[15][15];

    rais(base,n-15,ans,mod);

    

    lli final=0;

    

    for(int i=0;i<15;i++)

     {

     

      lli temp=mulmod(dp[15-i],ans[i][0],mod);

      while(temp<0) temp+=mod;

      final=(final+temp)%mod;

      while(final<0) final+=mod;

     

}

return final;

 }

};

int main()

{

 cin>>n;

//int k;

 cin>>k;

 int maxi=0;

 for(int i=0;i<k;i++)

 {

  int a;

  cin>>a;

  has[a]=1;

  v.push_back(a);

  maxi=max(maxi,a);

 }

 memset(dp,-1,sizeof dp);

 dp[0]=1;

 

 for(int i=1;i<=15;i++)

  {

  lli ans=0;

   for(int j=0;j<k;j++)

      {

       if(i-v[j]>=0)

             {

   ans+=dp[i-v[j]];  

       

 }

}

dp[i]=ans;

  }

  if(n<=15)

  {

  cout<<dp[n]*2<<endl;

  return 0;

  }

  else

  {

 

 expo ob;

 

 lli temp=ob.fibo(n,mod);

 temp=(1ll*temp*2);

 while(temp<0) temp+=mod;

cout<<temp%mod<<endl;

  }

}