Path Sum III variant on N-ary Tree

Given the root root of an N-ary tree and an integer targetSum, count the number of downward paths such that the sum of node values along the path equals targetSum. Rules: A path must go from parent to child (downward only). A path can start at any node and end at any node. Path length is at least 1. Return the number of such paths. I/O Convention (for coding) Node structure can be defined as: val: int children: List[Node] Output: an integer count. Suggested Constraints Number of nodes N: 1 <= N <= 1e5 Node values: -1e9 <= val <= 1e9 targetSum: -1e9 <= targetSum <= 1e9 Sample Tests 1 -> [2,3], 2 -> [4], targetSum=3 => 2 0 -> [0,0], targetSum=0 => 5 Single node 5, targetSum=5 => 1 -1 -> [-1,-1], targetSum=-2 => 2 1 -> [2,-1], 2 -> [-1], targetSum=1 => 2 Example Input (conceptual) root=1 children=[2,3], 2 children=[4], targetSum=3 Output 2