# PBinfo #3946 – CainiSiPisici3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Avem la dispoziție oricâți căței și oricâte pisici, câte așezări ale acestora în linie dreaptă de lungime n există astfel incât să nu avem o pisică între 2 căței și configurația să înceapă cu un câine și să se termine cu o pisică? Răspunsul se afișează modulo \(10^9+7\).

Date de intrare
Programul citește de la tastatură numărul n.

Date de ieșire
Programul va afișa pe ecran răspunsul.

Restricții și precizări

2 ≤ n ≤ 1.000.000.

Exemplu:
Intrare

3
Ieșire

2
Explicație
Configurațile sunt:
CPP
CCP

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
using namespace std;
ifstream fin("window.in");
ofstream fout("window.out");
const int mod=1e9+7;
int dp[1000005][2];
int main(){
    dp[1][0]=1;
    dp[1][1]=0;
    dp[2][0]=1;
    dp[2][1]=1;
    int n;
    cin>>n;
    for(int i=3;i<=n;i++){
        dp[i][0]=dp[i-1][0]+dp[i-2][1];
        if(dp[i][0]>=mod)dp[i][0]-=mod;
        dp[i][1]=dp[i-1][0]+dp[i-1][1];
        if(dp[i][1]>=mod)dp[i][1]-=mod;
    }
    cout<<dp[n][1];
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3946)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3946/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3946/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)