FPEvalDataset/LeetCodeProblem
0304
1{2 "id": 3659,3 "name": "count_paths_with_the_given_xor_value",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/count-paths-with-the-given-xor-value/",6 "date": "2024-12-07 00:00:00",7 "task_description": "You are given a 2D integer array `grid` with size `m x n`. You are also given an integer `k`. Your task is to calculate the number of paths you can take from the top-left cell `(0, 0)` to the bottom-right cell `(m - 1, n - 1)` satisfying the following **constraints**: You can either move to the right or down. Formally, from the cell `(i, j)` you may move to the cell `(i, j + 1)` or to the cell `(i + 1, j)` if the target cell _exists_. The `XOR` of all the numbers on the path must be **equal** to `k`. Return the total number of such paths. Since the answer can be very large, return the result **modulo** `109 + 7`. **Example 1:** **Input:** grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11 **Output:** 3 **Explanation:** The 3 paths are: `(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2)` `(0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)` `(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)` **Example 2:** **Input:** grid = [[1, 3, 3, 3], [0, 3, 3, 2], [3, 0, 1, 1]], k = 2 **Output:** 5 **Explanation:** The 5 paths are: `(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (2, 3)` `(0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) → (2, 3)` `(0, 0) → (1, 0) → (1, 1) → (1, 2) → (1, 3) → (2, 3)` `(0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2) → (2, 3)` `(0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (2, 3)` **Example 3:** **Input:** grid = [[1, 1, 1, 2], [3, 0, 3, 2], [3, 0, 2, 2]], k = 10 **Output:** 0 **Constraints:** `1 <= m == grid.length <= 300` `1 <= n == grid[r].length <= 300` `0 <= grid[r][c] < 16` `0 <= k < 16`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11",12 "output": "3 "13 },14 {15 "label": "Example 2",16 "input": "grid = [[1, 3, 3, 3], [0, 3, 3, 2], [3, 0, 1, 1]], k = 2",17 "output": "5 "18 },19 {20 "label": "Example 3",21 "input": "grid = [[1, 1, 1, 2], [3, 0, 3, 2], [3, 0, 2, 2]], k = 10",22 "output": ""23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 [30 6,31 11,32 14,33 11,34 13,35 13,36 9,37 3,38 4,39 14,40 4,41 4,42 2,43 13,44 1,45 3,46 11,47 8,48 9,49 3,50 6,51 11,52 11,53 0,54 7,55 13,56 5,57 11,58 12,59 12,60 4,61 1,62 15,63 4,64 0,65 6,66 10,67 8,68 0,69 6,70 10,71 14,72 7,73 2,74 15,75 5,76 5,77 13,78 15,79 2,80 2,81 15,82 5,83 0,84 12,85 8,86 1,87 9,88 3,89 9,90 1491 ],92 [93 15,94 9,95 15,96 7,97 8,98 10,99 0,100 6,101 10,102 0,103 8,104 11,105 11,106 0,107 4,108 1,109 2,110 10,111 9,112 12,113 13,114 7,115 3,116 10,117 1,118 4,119 7,120 14,121 4,122 11,123 12,124 10,125 4,126 9,127 15,128 2,129 0,130 8,131 2,132 13,133 10,134 3,135 8,136 12,137 3,138 13,139 12,140 12,141 5,142 11,143 8,144 0,145 1,146 7,147 1,148 8,149 0,150 1,151 1,152 3,153 3154 ],155 [156 12,157 3,158 10,159 1,160 2,161 14,162 15,163 7,164 9,165 3,166 11,167 0,168 14,169 10,170 4,171 1,172 7,173 2,174 1,175 3,176 15,177 2,178 8,179 6,180 9,181 4,182 3,183 9,184 10,185 11,186 14,187 2,188 0,189 0,190 5,191 11,192 15,193 14,194 11,195 8,196 4,197 6,198 13,199 7,200 2,201 14,202 0,203 5,204 15,205 2,206 12,207 5,208 1,209 5,210 5,211 13,212 9,213 0,214 4,215 12,216 6217 ],218 [219 7,220 3,221 11,222 5,223 4,224 10,225 3,226 4,227 3,228 11,229 5,230 9,231 10,232 0,233 8,234 1,235 4,236 13,237 1,238 9,239 10,240 9,241 1,242 0,243 2,244 14,245 12,246 7,247 9,248 6,249 7,250 15,251 2,252 13,253 14,254 14,255 7,256 14,257 4,258 1,259 5,260 10,261 13,262 3,263 2,264 7,265 13,266 9,267 0,268 7,269 14,270 2,271 8,272 5,273 13,274 6,275 1,276 9,277 7,278 4,279 4280 ],281 [282 0,283 4,284 0,285 7,286 6,287 10,288 9,289 3,290 4,291 1,292 2,293 3,294 6,295 1,296 11,297 12,298 1,299 6,300 10,301 7,302 3,303 15,304 9,305 4,306 12,307 10,308 7,309 1,310 0,311 7,312 5,313 12,314 3,315 14,316 9,317 7,318 14,319 12,320 4,321 11,322 14,323 3,324 14,325 2,326 14,327 13,328 9,329 13,330 8,331 3,332 3,333 12,334 13,335 13,336 0,337 2,338 15,339 9,340 7,341 2,342 4343 ],344 [345 10,346 0,347 0,348 12,349 14,350 10,351 5,352 13,353 5,354 1,355 8,356 2,357 15,358 11,359 0,360 12,361 13,362 0,363 2,364 12,365 4,366 14,367 0,368 14,369 6,370 12,371 12,372 15,373 4,374 0,375 5,376 10,377 10,378 13,379 7,380 15,381 10,382 13,383 10,384 0,385 9,386 5,387 10,388 8,389 15,390 13,391 4,392 4,393 7,394 0,395 5,396 3,397 12,398 12,399 14,400 3,401 4,402 4,403 6,404 6,405 15406 ],407 [408 6,409 9,410 9,411 12,412 5,413 4,414 7,415 2,416 6,417 4,418 3,419 8,420 5,421 1,422 14,423 13,424 4,425 13,426 0,427 8,428 8,429 2,430 6,431 3,432 8,433 9,434 11,435 12,436 9,437 8,438 2,439 12,440 13,441 0,442 13,443 11,444 10,445 3,446 10,447 5,448 15,449 5,450 7,451 6,452 11,453 0,454 0,455 13,456 13,457 12,458 9,459 11,460 2,461 7,462 13,463 13,464 1,465 6,466 11,467 2,468 3469 ],470 [471 9,472 12,473 4,474 4,475 14,476 8,477 1,478 0,479 13,480 11,481 7,482 3,483 11,484 2,485 4,486 5,487 15,488 2,489 4,490 8,491 9,492 15,493 14,494 8,495 14,496 12,497 14,498 6,499 12,500 13,501 1,502 9,503 13,504 8,505 4,506 12,507 0,508 5,509 5,510 0,511 5,512 5,513 7,514 4,515 1,516 0,517 12,518 11,519 13,520 14,521 10,522 9,523 13,524 8,525 2,526 15,527 14,528 7,529 10,530 8,531 5532 ],533 [534 0,535 12,536 2,537 12,538 15,539 5,540 10,541 5,542 10,543 6,544 1,545 6,546 4,547 1,548 3,549 4,550 15,551 13,552 10,553 10,554 12,555 8,556 15,557 2,558 3,559 9,560 15,561 3,562 6,563 7,564 9,565 0,566 13,567 14,568 6,569 12,570 1,571 7,572 10,573 6,574 2,575 13,576 3,577 1,578 5,579 14,580 13,581 14,582 12,583 0,584 13,585 9,586 2,587 14,588 12,589 4,590 14,591 0,592 14,593 15,594 6595 ],596 [597 9,598 9,599 8,600 11,601 12,602 4,603 9,604 2,605 7,606 15,607 11,608 6,609 7,610 1,611 0,612 9,613 2,614 4,615 1,616 14,617 9,618 1,619 11,620 5,621 10,622 6,623 7,624 12,625 8,626 1,627 13,628 14,629 14,630 13,631 12,632 0,633 8,634 13,635 8,636 13,637 13,638 5,639 13,640 10,641 3,642 0,643 12,644 7,645 8,646 8,647 4,648 5,649 8,650 10,651 2,652 14,653 8,654 10,655 12,656 1,657 9658 ],659 [660 9,661 14,662 5,663 12,664 5,665 8,666 15,667 8,668 4,669 7,670 10,671 11,672 1,673 6,674 5,675 1,676 2,677 7,678 10,679 11,680 7,681 2,682 4,683 5,684 0,685 6,686 0,687 4,688 3,689 5,690 9,691 5,692 7,693 14,694 8,695 14,696 12,697 0,698 12,699 5,700 4,701 9,702 3,703 11,704 10,705 7,706 2,707 0,708 5,709 10,710 14,711 4,712 11,713 11,714 6,715 2,716 10,717 4,718 3,719 14,720 15721 ],722 [723 5,724 13,725 8,726 1,727 12,728 0,729 10,730 9,731 5,732 3,733 9,734 11,735 7,736 10,737 4,738 12,739 12,740 14,741 4,742 9,743 3,744 11,745 5,746 2,747 10,748 13,749 4,750 12,751 10,752 11,753 8,754 1,755 2,756 12,757 11,758 10,759 14,760 3,761 14,762 13,763 13,764 8,765 8,766 2,767 8,768 5,769 2,770 12,771 7,772 15,773 13,774 7,775 4,776 9,777 1,778 12,779 7,780 10,781 1,782 6,783 6784 ],785 [786 3,787 3,788 12,789 1,790 0,791 5,792 7,793 9,794 15,795 10,796 1,797 10,798 13,799 14,800 12,801 3,802 8,803 10,804 14,805 15,806 2,807 3,808 6,809 3,810 1,811 8,812 4,813 6,814 15,815 4,816 12,817 4,818 4,819 11,820 15,821 13,822 11,823 13,824 1,825 8,826 2,827 7,828 0,829 2,830 13,831 3,832 6,833 7,834 15,835 12,836 2,837 1,838 9,839 14,840 9,841 9,842 0,843 12,844 9,845 14,846 8847 ],848 [849 13,850 0,851 3,852 5,853 0,854 2,855 8,856 15,857 7,858 1,859 5,860 13,861 9,862 11,863 15,864 6,865 2,866 2,867 0,868 14,869 9,870 3,871 1,872 0,873 6,874 4,875 7,876 13,877 0,878 13,879 12,880 11,881 0,882 6,883 15,884 14,885 7,886 12,887 13,888 15,889 10,890 15,891 2,892 4,893 7,894 8,895 3,896 11,897 7,898 5,899 7,900 12,901 10,902 14,903 0,904 11,905 11,906 10,907 3,908 10,909 13910 ],911 [912 6,913 4,914 7,915 10,916 0,917 9,918 4,919 2,920 5,921 4,922 2,923 5,924 3,925 9,926 14,927 4,928 4,929 12,930 15,931 6,932 0,933 5,934 0,935 6,936 5,937 12,938 3,939 2,940 2,941 12,942 3,943 6,944 13,945 14,946 7,947 4,948 0,949 6,950 9,951 7,952 7,953 7,954 2,955 5,956 13,957 12,958 9,959 5,960 10,961 12,962 12,963 5,964 3,965 13,966 14,967 1,968 14,969 3,970 11,971 10,972 4973 ],974 [975 4,976 12,977 5,978 2,979 8,980 3,981 14,982 2,983 4,984 8,985 10,986 12,987 6,988 11,989 14,990 1,991 13,992 3,993 4,994 3,995 3,996 9,997 2,998 2,999 10,1000 4,1001 0,1002 9,1003 4,1004 12,1005 0,1006 1,1007 1,1008 4,1009 3,1010 2,1011 14,1012 6,1013 2,1014 11,1015 5,1016 4,1017 5,1018 3,1019 2,1020 6,1021 2,1022 4,1023 5,1024 2,1025 0,1026 7,1027 3,1028 1,1029 15,1030 10,1031 13,1032 14,1033 11,1034 15,1035 31036 ],1037 [1038 1,1039 14,1040 14,1041 10,1042 5,1043 4,1044 4,1045 0,1046 5,1047 4,1048 13,1049 12,1050 4,1051 5,1052 14,1053 1,1054 10,1055 4,1056 9,1057 6,1058 0,1059 11,1060 8,1061 2,1062 1,1063 2,1064 12,1065 2,1066 4,1067 13,1068 5,1069 11,1070 7,1071 0,1072 7,1073 9,1074 8,1075 8,1076 5,1077 10,1078 11,1079 15,1080 9,1081 13,1082 1,1083 7,1084 2,1085 6,1086 6,1087 13,1088 0,1089 10,1090 12,1091 6,1092 15,1093 3,1094 2,1095 4,1096 13,1097 0,1098 31099 ],1100 [1101 13,1102 10,1103 12,1104 8,1105 7,1106 9,1107 10,1108 14,1109 12,1110 14,1111 1,1112 3,1113 9,1114 0,1115 4,1116 15,1117 4,1118 4,1119 9,1120 8,1121 8,1122 14,1123 7,1124 9,1125 3,1126 8,1127 10,1128 2,1129 15,1130 8,1131 2,1132 8,1133 13,1134 15,1135 4,1136 8,1137 1,1138 8,1139 0,1140 13,1141 4,1142 0,1143 7,1144 7,1145 5,1146 12,1147 15,1148 14,1149 6,1150 10,1151 5,1152 8,1153 5,1154 5,1155 4,1156 3,1157 14,1158 5,1159 4,1160 6,1161 51162 ],1163 [1164 7,1165 11,1166 5,1167 7,1168 15,1169 2,1170 14,1171 11,1172 9,1173 10,1174 15,1175 1,1176 13,1177 6,1178 9,1179 0,1180 6,1181 12,1182 1,1183 12,1184 5,1185 13,1186 0,1187 13,1188 12,1189 4,1190 4,1191 9,1192 6,1193 0,1194 7,1195 6,1196 6,1197 12,1198 7,1199 4,1200 9,