Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- const int mod = 1e9 + 7;
- const int inv2 = 500000004;
- struct Mint {
- int z;
- Mint() : z(0) {}
- Mint(int _z) : z(_z) {}
- Mint operator-(const Mint& other) const {
- int val = z - other.z + mod;
- if (val >= mod) { val -= mod; }
- return Mint(val);
- }
- Mint operator-(const int& other) const {
- int val = z - other + mod;
- if (val >= mod) { val -= mod; }
- return Mint(val);
- }
- Mint operator+(const Mint& other) const {
- int val = z + other.z;
- if (val >= mod) { val -= mod; }
- return Mint(val);
- }
- Mint operator+(const int& other) const {
- int val = z + other;
- if (val >= mod) { val -= mod; }
- return Mint(val);
- }
- Mint operator*(const Mint& other) const {
- int val = (1ll * z * other.z) % mod;
- return Mint(val);
- }
- Mint operator*(const int& other) const {
- int val = (1ll * z * other) % mod;
- return Mint(val);
- }
- };
- int k;
- vector<vector<int>> gr;
- vector<Mint> dp[2];
- void dfs(int v, int p) {
- vector<Mint> dp2[2];
- for (int _ = 0; _ <= 1; _++) {
- dp2[_].resize(k + 1);
- }
- dp2[0][0] = Mint(1);
- dp[0][v] = 1;
- int ind = 1;
- for (int& u : gr[v]) {
- if (u == p) {
- continue;
- }
- dfs(u, v);
- dp[0][v] = (dp[0][v] * (dp[1][u] + dp[0][u]));
- for (int i = 0; i <= k; i++) {
- dp2[ind][i] = (dp2[ind ^ 1][i] * (dp[0][u] + dp[1][u]));
- if (i) {
- dp2[ind][i] = (dp2[ind][i] + (dp2[ind ^ 1][i - 1] * dp[0][u]));
- }
- }
- dp2[ind ^ 1] = dp2[ind];
- ind ^= 1;
- }
- for (int i = 2; i <= k - 1; i++) {
- dp[1][v] = dp[1][v] + dp2[ind][i];
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n; cin >> n >> k;
- gr.resize(n);
- dp[0].resize(n, Mint());
- dp[1].resize(n, Mint());
- for (int u = 1; u < n; u++) {
- int v; cin >> v; v--;
- gr[v].push_back(u);
- }
- dfs(0, 0);
- cout << (dp[0][0] + dp[1][0]).z;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement