#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MOD = 1e9 + 7;

void countShortestPaths(int n, vector<vector<int>>& adj) {
    // Initialize dist with -1 (unvisited)
    vector<int> dist(n + 1, -1);
    vector<int> ways(n + 1, 0);
    
    queue<int> q;
    
    // Start from node 1
    dist[1] = 0;
    ways[1] = 1;
    q.push(1);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            // 1. First time reaching 'v' (unvisited)
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                ways[v] = ways[u];
                q.push(v);
            } 
            // 2. Found another shortest path to 'v'
            else if (dist[v] == dist[u] + 1) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    
    // Output the number of ways to reach each node
    for (int i = 1; i <= n; i++) {
        cout << "Node " << i << ": " << ways[i] << " ways\n";
    }
}
int main(){}