#include <iostream>
using namespace std;

// Definition for singly-linked list node
class Node {
public:
    int data;
    Node* next;
    
    // Constructor
    Node(int val) {
        data = val;
        next = NULL;
    }
};

// Function to find the last node in the linked list such that position % K == 0
Node* modularNode(Node* head, int k) {
    // Edge cases
    if (head == NULL || k <= 0)
        return NULL;
    
    Node* result = NULL;
    int position = 1;
    
    // Traverse the linked list
    Node* current = head;
    while (current != NULL) {
        // If current position is divisible by k, update result
        if (position % k == 0)
            result = current;
        
        // Move to next node and increment position
        current = current->next;
        position++;
    }
    
    return result;
}

// Utility function to create a linked list from array
Node* createLinkedList(int arr[], int n) {
    if (n == 0) return NULL;
    
    Node* head = new Node(arr[0]);
    Node* current = head;
    
    for (int i = 1; i < n; i++) {
        current->next = new Node(arr[i]);
        current = current->next;
    }
    
    return head;
}

// Utility function to print a linked list
void printLinkedList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        cout << current->data;
        if (current->next != NULL)
            cout << " -> ";
        current = current->next;
    }
    cout << endl;
}

// Test cases
void runTestCase(int testNum, int arr[], int n, int k, int expectedValue) {
    Node* head = createLinkedList(arr, n);
    
    cout << "Test Case " << testNum << ":" << endl;
    cout << "Linked List: ";
    printLinkedList(head);
    cout << "K = " << k << endl;
    
    Node* result = modularNode(head, k);
    
    if (result == NULL) {
        cout << "Result: NULL" << endl;
        if (expectedValue == -1)
            cout << "Test PASSED" << endl;
        else
            cout << "Test FAILED. Expected: " << expectedValue << ", Got: NULL" << endl;
    } else {
        cout << "Result: Node with value " << result->data << endl;
        if (result->data == expectedValue)
            cout << "Test PASSED" << endl;
        else
            cout << "Test FAILED. Expected: " << expectedValue << ", Got: " << result->data << endl;
    }
    cout << "----------------------" << endl;
    
    // Clean up memory
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    // Test Case 1: Example from the problem
    // N = 7, K = 3
    // Linked List = 1 -> 3 -> 2 -> 4 -> 6 -> 5 -> 7
    int arr1[] = {1, 3, 2, 4, 6, 5, 7};
    runTestCase(1, arr1, 7, 3, 6);
    
    // Test Case 2: Another example
    // Linked List = 3 -> 7 -> 1 -> 9 -> 8
    // K = 2
    int arr2[] = {3, 7, 1, 9, 8};
    runTestCase(2, arr2, 5, 2, 9);
    
    // Test Case 3: K larger than list length
    int arr3[] = {5, 8, 3, 1};
    runTestCase(3, arr3, 4, 5, -1);
    
    // Test Case 4: K = 1 (every node is modular)
    int arr4[] = {2, 4, 6, 8};
    runTestCase(4, arr4, 4, 1, 8);
    
    // Test Case 5: Single element list
    int arr5[] = {10};
    runTestCase(5, arr5, 1, 1, 10);
    
    // Test Case 6: Empty list
    runTestCase(6, NULL, 0, 3, -1);
    
    // Test Case 7: Invalid K
    int arr7[] = {1, 2, 3};
    runTestCase(7, arr7, 3, 0, -1);
    
    return 0;
}