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

using namespace std;

const int MOD = 1e9 + 7;

void countOptimalPaths(int n, vector<vector<int>>& adj, vector<int>& val) {
    vector<int> dist(n + 1, -1);
    vector<int> max_fives(n + 1, 0);
    vector<int> ways(n + 1, 0);
    
    queue<int> q;
    
    // Base Case for Node 1
    dist[1] = 0;
    max_fives[1] = (val[1] == 5 ? 1 : 0);
    ways[1] = 1;
    q.push(1);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            int is_five = (val[v] == 5 ? 1 : 0);
            int new_fives = max_fives[u] + is_five;
            
            // 1. First time visiting 'v' (guaranteed shortest path)
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                max_fives[v] = new_fives;
                ways[v] = ways[u];
                q.push(v);
            } 
            // 2. Found an alternative shortest path to 'v'
            else if (dist[v] == dist[u] + 1) {
                
                // Case A: This path has STRICTLY MORE 5s
                if (new_fives > max_fives[v]) {
                    max_fives[v] = new_fives;
                    ways[v] = ways[u]; // Reset ways (previous paths were suboptimal)
                } 
                // Case B: This path has the EXACT SAME maximum 5s
                else if (new_fives == max_fives[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD; // Accumulate ways
                }
                
                // Case C: new_fives < max_fives[v]
                // We do nothing, because this path has fewer 5s than our current best
            }
        }
    }
    
    // Output the results
    for (int i = 1; i <= n; i++) {
        if (dist[i] != -1) {
            cout << "Node " << i << " -> Shortest Path length: " << dist[i] 
                 << ", Max 5s: " << max_fives[i] 
                 << ", Number of such optimal paths: " << ways[i] << "\n";
        } else {
            cout << "Node " << i << " -> Unreachable\n";
        }
    }
}
int main(){}